Count Number of Homogenous Substrings — Problem & Solution
Count Number of Homogenous Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Number of Homogenous Substrings is a medium coding problem on strings and math, asked in Amazon, Google and Oracle interviews.
- Difficulty: Medium
- Topics: Strings, Math
- Asked at: Amazon, Google, Oracle
- 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
A string is homogenous when all of its characters are the same.
Return the number of homogenous substrings of s, modulo 10⁹ + 7.
Example 1
Input: s = "codekairo"
Output: 9
Explanation: No two adjacent characters match, so only the nine single characters qualify.
Example 2
Input: s = "abbcccaa"
Output: 13
Explanation: 1 + 3 + 6 + 3 — each run of length `L` contributes `L(L+1)/2`.
Example 3
Input: s = "zzzzz"
Output: 15
Constraints
1 <= s.length <= 10^5s consists of lowercase letters.
Hints for Count Number of Homogenous Substrings
Hint 1
Every homogenous substring lies inside a maximal run of one repeated character.
Hint 2
A run of length
LcontainsL * (L + 1) / 2substrings.Hint 3
Equivalently, sweep once and add the current run length at every position.
How to solve Count Number of Homogenous Substrings
Count substrings by their right endpoint. At position i, the number of homogenous substrings ending there equals the length of the run of equal characters ending at i. Sum those, modulo 10⁹ + 7.
Approach
- Keep
run, reset to 1 whenever the character differs from the previous one, incremented otherwise. - Add
runto a running total at every position, taking the modulo.
Why it works
Counting by right endpoint turns the run formula L(L+1)/2 into a single accumulation — you never have to find the run boundaries or multiply anything, and the total never exceeds the modulus between steps. The formula version is equivalent, but needs 64-bit arithmetic for L(L+1)/2 before the modulo when L is large.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The result must be taken modulo 10⁹ + 7 — the raw count overflows 32 bits at the upper bound.
runresets to 1, not 0, on a change of character.- Single characters are homogenous substrings and must be counted.
Reference solution
Python
def countHomogenous(s: str) -> int:
MOD = 10**9 + 7
total = 0
run = 0
for i, c in enumerate(s):
run = run + 1 if i > 0 and c == s[i - 1] else 1
total = (total + run) % MOD
return totalJava
public static int countHomogenous(String s) {
final long MOD = 1000000007L;
long total = 0;
long run = 0;
for (int i = 0; i < s.length(); i++) {
run = (i > 0 && s.charAt(i) == s.charAt(i - 1)) ? run + 1 : 1;
total = (total + run) % MOD;
}
return (int) total;
}C++
int countHomogenous(string s) {
const long long MOD = 1000000007LL;
long long total = 0, run = 0;
for (size_t i = 0; i < s.size(); i++) {
run = (i > 0 && s[i] == s[i - 1]) ? run + 1 : 1;
total = (total + run) % MOD;
}
return (int) total;
}JavaScript
var countHomogenous = function(s) {
var MOD = 1000000007;
var total = 0, run = 0;
for (var i = 0; i < s.length; i++) {
run = i > 0 && s.charAt(i) === s.charAt(i - 1) ? run + 1 : 1;
total = (total + run) % MOD;
}
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