Count Substrings with Only One Distinct Letter - Solution & Explanation
Problem Statement
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.
Approach Overview
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.
Approach 1: Two Pointers
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).
Code
Python
Java
C++
Go
TypeScript
Approach 2: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Two Pointers | — |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
LeetCode 1180. Count Substrings with Only One Distinct Letter Python • TechZoo • 800 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Count Substrings with Only One Distinct Letter easy or hard?
Count Substrings with Only One Distinct Letter Python/Java solution
How to solve Count Substrings with Only One Distinct Letter in O(n)?
What is the best approach for Count Substrings with Only One Distinct Letter?
Is Count Substrings with Only One Distinct Letter asked at Google/Amazon/Meta?
What data structure is used in Count Substrings with Only One Distinct Letter?
What is the time complexity of Count Substrings with Only One Distinct Letter?
Ready to solve this problem?
Practice Count Substrings with Only One Distinct Letter with our built-in code editor and test cases.
Practice on FleetCode