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).
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 ; } }Video 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.