💬 Discord
Sign In
NeetCode #896LC-1180EasyMath & GeometryNC Algo100
← Back to All Problems

#896 · #1180 · Count Substrings with Only One Distinct Letter(统计只含单一字母的子串)

📌 Problem Statement & Constraints

Given a string s, return the number of substrings that contain only one distinct letter, meaning every character in the substring is the same. Constraints: 1 <= s.length <= 10^5, s consists of lowercase English letters.

💡 Core Algorithmic Approaches

  1. Every maximal run of identical characters of length L contributes L * (L + 1) / 2 valid substrings, one per contiguous sub-run.
  2. Scan the string while tracking the length of the current run.
  3. When the run ends -- either because the character changes or because the string ends -- add its triangular number to the total and reset the run length to one.
  4. Summing over all runs counts every valid substring exactly once.

💻 Benchmark Python3 Implementation

class Solution:
    def countLetters(self, s: str) -> int:
        total = 0
        run = 1
        for i in range(1, len(s) + 1):
            if i < len(s) and s[i] == s[i - 1]:
                run += 1
            else:
                total += run * (run + 1) // 2   # all sub-runs of this run
                run = 1
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass over the string.
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Counting only the maximal runs: every sub-run also qualifies, which is exactly why the triangular number is used.
  • Forgetting to flush the final run: the loop runs one index past the end precisely to handle the last run.
  • Resetting run before adding the triangular number: the run length is needed at the moment the run ends.
  • Using L * (L - 1) // 2: the number of contiguous substrings of a length-L run is L * (L + 1) // 2, which counts the single characters too.