Count Number of Homogenous Substrings
MedPrompt
Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 109 + 7.
A string is homogenous if all the characters of the string are the same.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
"a" appears 3 times.
"aa" appears 1 time.
"b" appears 2 times.
"bb" appears 1 time.
"c" appears 3 times.
"cc" appears 2 times.
"ccc" appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.Example 2:
Input: s = "xy"
Output: 2
Explanation: The homogenous substrings are "x" and "y".Example 3:
Input: s = "zzzzz"
Output: 15
Constraints:
1 <= s.length <= 105sconsists of lowercase letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves generating all possible substrings of the input string s and checking if each substring is homogenous. A substring is homogenous if all its characters are identical. We can use two nested loops to define the start and end points of each substring.
Algorithm
- Initialize
totalCount = 0andMOD = 1_000_000_007. - Iterate through the string with an index
ifrom0tolength - 1. - For each
i, start an inner loop with an indexjfromitolength - 1. - Check if the character at
jis the same as the character ati. - If they are the same, it means the substring from
itojis homogenous. IncrementtotalCountand apply modulo. - If they are different, break the inner loop, as any further substring starting at
iwill not be homogenous. - After the loops complete, return
totalCount.
Walkthrough
We iterate through the string with an outer loop using index i from 0 to n-1, where n is the length of the string. The index i represents the starting position of a potential homogenous substring.
For each i, we start an inner loop with index j from i to n-1.
The substring from i to j is homogenous if s.charAt(j) is the same as s.charAt(i).
If they are the same, we have found one homogenous substring, so we increment our total count.
If s.charAt(j) is different from s.charAt(i), it means the substring s.substring(i, j+1) is not homogenous. Furthermore, any longer substring starting at i will also not be homogenous. Therefore, we can break the inner loop and continue with the next starting position i+1.
We keep a running total of the count, applying the modulo operation at each addition to prevent integer overflow.
The final count is the answer.
class Solution { public int countHomogenous(String s) { int n = s.length(); long totalCount = 0; int MOD = 1_000_000_007; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (s.charAt(j) == s.charAt(i)) { totalCount = (totalCount + 1) % MOD; } else { break; } } } return (int) totalCount; }}Complexity
Time
O(N^2), where N is the length of the string. In the worst-case scenario (e.g., a string like "aaaaa"), the inner loop runs N times for each iteration of the outer loop.
Space
O(1), as we only use a few variables to store the count and loop indices.
Trade-offs
Pros
Relatively straightforward to understand and implement.
Doesn't require complex data structures.
Cons
Inefficient for large inputs. It will result in a "Time Limit Exceeded" error for the given constraints (N up to 10^5).
A more efficient approach is to iterate through the string just once. We can count the lengths of consecutive blocks of identical characters. For a block of k identical characters, it contributes k * (k + 1) / 2 homogenous substrings. However, a simpler way to achieve the same result is to maintain a streak counter.
Algorithm
- Initialize
ans = 0,currentStreak = 0, andMOD = 1_000_000_007. - Iterate through the string
swith an indexifrom0tolength - 1. - Inside the loop, check if it's the first character (
i == 0) or if the current characters.charAt(i)is the same as the previous characters.charAt(i - 1). - If they are the same, increment
currentStreak. - If they are different, a new homogenous block has started, so reset
currentStreakto1. - Add the
currentStreaktoansand take the result moduloMOD. - After the loop finishes,
answill hold the total count of homogenous substrings. Returnans.
Walkthrough
We iterate through the string from left to right, keeping track of the length of the current consecutive streak of identical characters.
Let's use a variable streak to store this length.
We initialize a result variable ans to 0.
For each character s.charAt(i), we compare it with the previous character s.charAt(i-1).
If i > 0 and s.charAt(i) is the same as s.charAt(i-1), it means the streak continues. We increment streak.
If it's the first character (i == 0) or if s.charAt(i) is different from s.charAt(i-1), the streak is broken, and a new one starts. We reset streak to 1.
In each step of the iteration, we add the current streak value to our total ans. Why does this work? When we have a streak of length k, we are adding k to the total. This is because the new character forms k new homogenous substrings: one of length 1 (itself), and k-1 substrings by appending itself to the k-1 homogenous substrings ending at the previous position.
For example, for "aaa":
- 'a': streak=1, ans=1. (Substrings: "a")
- 'aa': streak=2, ans=1+2=3. (New substrings: "a", "aa". Total: "a", "a", "aa")
- 'aaa': streak=3, ans=3+3=6. (New substrings: "a", "aa", "aaa". Total: "a", "a", "a", "aa", "aa", "aaa")
The sum of streaks
1 + 2 + ... + kis exactlyk * (k + 1) / 2, which is the number of homogenous substrings in a block of lengthk. We must perform the addition modulo10^9 + 7to prevent overflow.
class Solution { public int countHomogenous(String s) { int MOD = 1_000_000_007; long ans = 0; int currentStreak = 0; for (int i = 0; i < s.length(); i++) { if (i == 0 || s.charAt(i) == s.charAt(i - 1)) { currentStreak++; } else { currentStreak = 1; } ans = (ans + currentStreak) % MOD; } return (int) ans; }}Complexity
Time
O(N), where N is the length of the string. We perform a single pass through the string.
Space
O(1), as we only use a constant amount of extra space for variables like `ans` and `currentStreak`.
Trade-offs
Pros
Highly efficient with linear time complexity.
Optimal solution for the given constraints.
Low memory usage.
Cons
The logic of adding the streak count might be slightly less intuitive than the brute-force method initially.
Solutions
Solution
public class Solution { public int CountHomogenous ( string s ) { long MOD = 1000000007 ; long ans = 0 ; for ( int i = 0 , j = 0 ; i < s . Length ; i = j ) { j = i ; while ( j < s . Length && s [ j ] == s [ i ]) { ++ j ; } int cnt = j - i ; ans += ( long ) ( 1 + cnt ) * cnt / 2 ; ans %= MOD ; } return ( int ) ans ; } }class Solution {private static final int MOD = (int)1 e9 + 7;public int countHomogenous(String s) { int n = s.length(); long ans = 0; for (int i = 0, j = 0; i < n; i = j) { j = i; while (j < n && s.charAt(j) == s.charAt(i)) { ++j; } int cnt = j - i; ans += (long)(1 + cnt) * cnt / 2; ans %= MOD; } return (int)ans; }}class Solution {public: const int mod = 1e9 + 7; int countHomogenous(string s) { int n = s.size(); long ans = 0; for (int i = 0, j = 0; i < n; i = j) { j = i; while (j < n && s[j] == s[i]) ++j; int cnt = j - i; ans += 1ll * (1 + cnt) * cnt / 2; ans %= mod; } return ans; }};class Solution: def countHomogenous(self, s: str) -> int: mod = 10 ** 9 + 7 i, n = 0, len(s) ans = 0 while i < n: j = i while j < n and s[j] == s[i]: j += 1 cnt = j - i ans += (1 + cnt) * cnt // 2 ans %= mod i = j return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.