leetcode - 1759. Count Number of Homogenous Substrings

Description

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 10^9 + 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.
1
2
3
4
5
6
7
8
9
10
11

Example 2:

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

Example 3:

Input: s = "zzzzz"
Output: 15
1
2

Constraints:

1 <= s.length <= 10^5
s consists of lowercase letters.
1
2

Solution

The most straightforward way is to count the frequency of each character in the string, then go through the string to count the answer.

But for example 1, when we encounter a, we could add 1, and when we encounter bb, we could add 2(number of b) and 1(number of bb), similarly, for ccc we add 3(number of c), 2(number of cc) and 1(number of ccc).

So instead of brute-force, we could go through the string, and compare the previous character and current character.

Time complexity: $o(n)$
Space complexity: $o(1)$

Code

class Solution:
    def countHomogenous(self, s: str) -> int:
        res = 0
        prev_c = None
        modulo = 1000000007
        for each_c in s:
            if each_c != prev_c:
                if prev_c:
                    res += (1 + cnt) * cnt // 2
                    res %= modulo
                prev_c = each_c
                cnt = 0
            cnt += 1
        return (res + (1 + cnt) * cnt // 2) % modulo
1
2
3
4
5
6
7
8
9
10
11
12
13
14