Given a string s, return the number of substrings that have only one distinct letter.
Example 1:
Input: s = "aaaba" Output: 8 Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b". "aaa" occurs 1 time. "aa" occurs 2 times. "a" occurs 4 times. "b" occurs 1 time. So the answer is 1 + 2 + 4 + 1 = 8.
Example 2:
Input: s = "aaaaaaaaaa" Output: 55
Constraints:
1 <= s.length <= 1000s[i] consists of only lowercase English letters.Problem Overview: Given a string s, count how many substrings contain only one distinct character. Any substring made entirely of the same letter is valid. For example, the run "aaa" contributes a, a, a, aa, aa, and aaa.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Generate every substring starting at index i. Extend the substring to the right while checking if all characters match the first character. The moment a different character appears, stop expanding that start index. Each valid extension contributes one substring to the answer. This approach directly models the problem but still checks up to n extensions for each index, resulting in O(n²) time. Useful for understanding the structure of valid substrings but inefficient for large strings.
Approach 2: Consecutive Run Counting (Math Insight) (O(n) time, O(1) space)
Instead of checking every substring, group consecutive identical characters. If a character repeats k times in a row, the number of valid substrings formed from that run is k * (k + 1) / 2. For example, the run "bbbb" produces 4 + 3 + 2 + 1 = 10 substrings. Iterate through the string, track the length of the current run, and add the formula when the run ends. This converts the problem into simple counting and uses basic math combined with linear scanning of the string.
Approach 3: Two Pointers / Sliding Window (O(n) time, O(1) space)
Use two pointers to maintain a window where all characters are identical. Start both pointers at the beginning. Move the right pointer forward while the character matches the left pointer’s character. Each extension adds (right - left + 1) new valid substrings ending at right. When the character changes, reset the left pointer to the new position. This is essentially a two pointers version of run counting and works well when you naturally think in terms of sliding windows.
Recommended for interviews: The consecutive run counting approach is the cleanest solution. It demonstrates that you recognize the combinatorial pattern in repeated characters and reduces the problem to a single linear scan. Starting with the brute force explanation shows understanding of the problem space, but interviewers expect the O(n) run-based or two-pointer optimization.
We can use two pointers, where pointer i points to the start of the current substring, and pointer j moves to the right to the first position that is different from s[i]. Then, [i,..j-1] is a substring with s[i] as the only character, and its length is j-i. Therefore, the number of substrings with s[i] as the only character is \frac{(j-i+1)(j-i)}{2}, which is added to the answer. Then, we set i=j and continue to traverse until i exceeds the range of string s.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Two Pointers | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Conceptual starting point or very small input sizes |
| Consecutive Run Counting (Math) | O(n) | O(1) | Best general solution; converts repeated characters into a combinatorial count |
| Two Pointers / Sliding Window | O(n) | O(1) | When implementing substring logic with pointer movement or window-based reasoning |
LeetCode 1180. Count Substrings with Only One Distinct Letter Python • TechZoo • 796 views views
Watch 5 more video solutions →Practice Count Substrings with Only One Distinct Letter with our built-in code editor and test cases.
Practice on FleetCode