#1759

Medium

LeetCode Problem Workspace

Count Number of Homogenous Substrings

This problem requires counting all homogenous substrings in a given string and returning the result modulo 10^9 + 7.

Problem Statement

You are given a string s, and you need to count the number of homogenous substrings of s. A string is homogenous if all characters within it are the same. You must return the total count of homogenous substrings modulo 10^9 + 7, as the result may be very large.

To clarify, a substring is a contiguous sequence of characters in the original string. A substring is considered homogenous if every character in it is identical. Your task is to compute the total count of all such substrings for the given string s.

Examples

Example 1

Input: s = "abbcccaa"

Output: 13

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

The homogenous substrings are "x" and "y".

Example 3

Input: s = "zzzzz"

Output: 15

Example details omitted.

Constraints

1 <= s.length <= 105
s consists of lowercase letters.

Solution Approach

Identify Contiguous Blocks

Start by identifying contiguous blocks of identical characters in the string. For each such block, the number of homogenous substrings is given by the formula k * (k + 1) / 2, where k is the length of the block. This is because a block of length k contributes k substrings of length 1, (k-1) substrings of length 2, and so on.

Summing the Substrings

Once you have the length of each block, sum up the substrings for each block using the formula described above. Ensure that the result remains within bounds by taking the sum modulo 10^9 + 7 at each step.

Efficient Iteration

Iterate through the string once, counting the length of contiguous blocks and calculating the substrings as you go. This allows the solution to run in linear time, O(n), ensuring it is efficient enough for large strings up to the length limit.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n), where n is the length of the string. We only traverse the string once, making the algorithm efficient. The space complexity is O(1) since we only need a few variables to track the current block length and total sum.

What Interviewers Usually Probe

Look for knowledge of string manipulation and efficient counting.
Evaluate the candidate's understanding of mathematical patterns and their application to this problem.
Check if the candidate can handle large inputs by optimizing the solution to O(n) time complexity.

Common Pitfalls or Variants

Common pitfalls

Forgetting to take the sum modulo 10^9 + 7 at each step can result in overflow errors.
Confusing the formula for the number of substrings, especially with blocks of length 1.
Not considering edge cases like strings with only one character or strings with all distinct characters.

Follow-up variants

Change the problem to return the total number of homogenous substrings of length greater than 1.
Modify the problem to work with strings containing uppercase letters.
Ask the candidate to solve the problem using a sliding window approach.

FAQ

What is a homogenous substring?

A homogenous substring is a substring in which all characters are the same.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the input string.

How do I calculate the number of substrings for a block of characters?

For a block of length k, the number of homogenous substrings is k * (k + 1) / 2.

What does modulo 10^9 + 7 mean in this problem?

Modulo 10^9 + 7 ensures the result remains within the range of integer limits, preventing overflow issues.

How does GhostInterview help with solving this problem?

GhostInterview assists by providing problem-specific suggestions, code templates, and guidance on mathematical patterns related to the problem.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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 ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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 ans

Continue Practicing

#1812 determine color of a chessboard square #1830 minimum number of operations to make string sorted #1896 minimum cost to change the final value of expression