Count Substrings with Only One Distinct Letter — Solution
Count Substrings with Only One Distinct Letter solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Substrings with Only One Distinct Letter is an easy coding problem on strings and math, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Math
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s, return the number of substrings that contain only one distinct letter.
Substrings are counted by position, so identical substrings occurring at different places count separately.
Example 1
Input: s = "aaaba"
Output: 8
Explanation: "aaa" contributes 6 substrings, plus "b" and the trailing "a".
Example 2
Input: s = "aaaaaaaaaa"
Output: 55
Explanation: A run of 10 gives 10·11/2 = 55.
Example 3
Input: s = "abc"
Output: 3
Constraints
1 <= s.length <= 1000s consists of lowercase English letters.
Hints for Count Substrings with Only One Distinct Letter
Hint 1
Every valid substring lies entirely inside a maximal run of equal characters.
Hint 2
A run of length
kcontainsk(k+1)/2substrings.Hint 3
Split the string into runs and sum that formula over them.
How to solve Count Substrings with Only One Distinct Letter
A substring with one distinct letter is a contiguous block of identical characters, so it must sit inside a maximal run. Counting the substrings of each run and summing gives the answer directly.
Approach
- Scan the string, extending a run counter while consecutive characters match.
- When the run ends (or the string does), add
run * (run + 1) / 2to the total. - Reset the run counter and continue.
Why it works
A run of length k has exactly one substring of length k, two of length k-1, …, k of length 1 — a triangular number, k(k+1)/2. Runs are disjoint, so their counts simply add.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Forgetting to flush the final run drops every substring in the last block.
- Enumerating all substrings is O(n²) and unnecessary.
k(k+1)/2fork = 1000is 500,500 — comfortably in range, but the productk*(k+1)should still be computed before the division.
Reference solution
Python
def countLetters(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
run = 1
return totalJava
public static int countLetters(String s) {
long total = 0;
int run = 1;
for (int i = 1; i <= s.length(); i++) {
if (i < s.length() && s.charAt(i) == s.charAt(i - 1)) run++;
else {
total += (long) run * (run + 1) / 2;
run = 1;
}
}
return (int) total;
}C++
int countLetters(string s) {
long long total = 0;
int run = 1;
for (int i = 1; i <= (int) s.size(); i++) {
if (i < (int) s.size() && s[i] == s[i - 1]) run++;
else {
total += (long long) run * (run + 1) / 2;
run = 1;
}
}
return (int) total;
}JavaScript
var countLetters = function(s) {
let total = 0, run = 1;
for (let i = 1; i <= s.length; i++) {
if (i < s.length && s.charAt(i) === s.charAt(i - 1)) run++;
else {
total += (run * (run + 1)) / 2;
run = 1;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings