Count Substrings with Only One Distinct Letter solution and explanation
5 more videos on this problem
LeetCode 1180. Count Substrings with Only One Distinct Letter PythonTechZoo · 6:00 · 800 views
Live Coding: Leetcode 1180. Count Substrings with Only One Distinct Letter Leetcode easyCS Live Coding · 14:36 · 725 views
Leetcode 1180. Count Substrings with Only One Distinct LetterLetsCode · 5:54 · 425 views
LeetCode 1180 | Count Substrings with Only One Distinct Letter | JavaSleepy Cracker · 4:48 · 190 views
1180. Count Substrings with Only One Distinct Letter (Leetcode Easy)Programming Live with Larry · 3:55 · 173 views
LeetCode 1180: Count Substrings with Only One Distinct LetterAlitaCode · 27:37 · 14 views
The problem
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).
class Solution:
def countLetters(self, s: str) -> int:
n = len(s)
i = ans = 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
ans += (1 + j - i) * (j - i) // 2
i = j
return ansclass Solution {
public int countLetters(String s) {
int ans = 0;
for (int i = 0, n = s.length(); i < n;) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) {
++j;
}
ans += (1 + j - i) * (j - i) / 2;
i = j;
}
return ans;
}
}class Solution {
public:
int countLetters(string s) {
int ans = 0;
for (int i = 0, n = s.size(); i < n;) {
int j = i;
while (j < n && s[j] == s[i]) {
++j;
}
ans += (1 + j - i) * (j - i) / 2;
i = j;
}
return ans;
}
};function countLetters(s: string): number {
let ans = 0;
const n = s.length;
for (let i = 0; i < n; ) {
let j = i;
let cnt = 0;
while (j < n && s[j] === s[i]) {
++j;
ans += ++cnt;
}
i = j;
}
return ans;
}func countLetters(s string) int {
ans := 0
for i, n := 0, len(s); i < n; {
j := i
for j < n && s[j] == s[i] {
j++
}
ans += (1 + j - i) * (j - i) / 2
i = j
}
return ans
}Approach 2: Default Approach
class Solution:
def countLetters(self, s: str) -> int:
ans = 0
i, n = 0, len(s)
while i < n:
j = i
cnt = 0
while j < n and s[j] == s[i]:
j += 1
cnt += 1
ans += cnt
i = j
return ansclass Solution {
public int countLetters(String s) {
int ans = 0;
int i = 0, n = s.length();
while (i < n) {
int j = i;
int cnt = 0;
while (j < n && s.charAt(j) == s.charAt(i)) {
++j;
ans += ++cnt;
}
i = j;
}
return ans;
}
}class Solution {
public:
int countLetters(string s) {
int ans = 0;
int i = 0, n = s.size();
while (i < n) {
int j = i;
int cnt = 0;
while (j < n && s[j] == s[i]) {
++j;
ans += ++cnt;
}
i = j;
}
return ans;
}
};func countLetters(s string) (ans int) {
i, n := 0, len(s)
for i < n {
j := i
cnt := 0
for j < n && s[j] == s[i] {
j++
cnt++
ans += cnt
}
i = j
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointers | – |
| Default Approach | – |
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 |
Frequently asked questions
Is Count Substrings with Only One Distinct Letter easy or hard?
Count Substrings with Only One Distinct Letter is classified as an Easy problem on LeetCode with an acceptance rate around 80%. The key insight is recognizing that consecutive identical characters form a combinatorial pattern, allowing a simple O(n) solution.
Count Substrings with Only One Distinct Letter Python/Java solution
Most implementations iterate through the string while tracking the length of the current identical-character run. Each time the run ends, add k * (k + 1) / 2 to the result. The same logic works in Python, Java, C++, and Go with O(n) time and O(1) space.
How to solve Count Substrings with Only One Distinct Letter in O(n)?
Traverse the string and track the length of the current block of identical characters. When a block ends, compute the number of substrings using k * (k + 1) / 2 and add it to the result. Continue scanning the string and repeat for each run, resulting in a single linear pass.
What is the best approach for Count Substrings with Only One Distinct Letter?
The optimal approach groups consecutive identical characters and counts substrings using the formula k * (k + 1) / 2 for each run of length k. This works because every substring inside that run contains the same character. The algorithm scans the string once, giving O(n) time complexity and O(1) space.
Is Count Substrings with Only One Distinct Letter asked at Google/Amazon/Meta?
Substring counting and sliding window patterns frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying concepts—string traversal, run-length counting, and two-pointer techniques—are common interview topics.
What data structure is used in Count Substrings with Only One Distinct Letter?
The solution primarily uses simple variables and string traversal. No complex data structures are required. The logic relies on counting consecutive characters, often implemented with counters or two pointers.
What is the time complexity of Count Substrings with Only One Distinct Letter?
The optimal solution runs in O(n) time where n is the length of the string. You iterate through the string once while tracking the length of consecutive identical characters. Space complexity is O(1) since only a few counters are needed.