Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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:

1
2
3

Input: s = "xy"
Output: 2
Explanation: The homogenous substrings are "x" and "y".

Example 3:

1
2

Input: s = "zzzzz"
Output: 15

Solution

Method 1 - Two pointer technique

To solve the problem of counting homogeneous substrings, we can use a two-pointer technique. The idea is to maintain a window of consecutive identical characters and count the homogeneous substrings within this window.

Approach

  1. Initialization:
    • Initialize a variable ans to store the result and a pointer l to mark the start of the current window of identical characters.
    • Define a constant MOD for the modulo operation.
  2. Iterate Through the String:
    • Use a pointer r to traverse through the string.
    • For each character, check if it is the same as the character at the start of the window (s[l]).
    • If it is, add the length of the current homogeneous substring window (r - l + 1) to ans.
    • If it is not, reset the start of the window to the current position (l = r) and count this new single character as a separate homogeneous substring.
    • Apply the modulo operation to ans at each step to ensure the result fits within the limit.
  3. Return the Result:
    • Return ans as an integer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	public int countHomogenous(String s) {
		long ans = 0;
		int l = 0;
		int MOD = (int) 1_000_000_000 + 7;
		for (int r = 0; r < s.length(); r++) {
			if(s.charAt(l) == s.charAt(r)) {
				ans += r - l + 1;
			} else {
				ans += 1;
				l = r;
			}
			ans = ans % MOD;
		}
	
		return (int)ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def countHomogenous(self, s: str) -> int:
        MOD = 10**9 + 7
        ans: int = 0
        l: int = 0
        
        for r in range(len(s)):
            if s[l] == s[r]:
                ans += r - l + 1
            else:
                l = r
                ans += 1
            ans %= MOD
        
        return ans

Complexity

  • Time: O(n), where n is the length of the string. We traverse the string once and perform constant-time operations within the loop.
  • Space: O(1), as we use a fixed amount of additional space for variables.