Count Number Of Homogenous Substrings - Leetcode Solution

Problem Statement:

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 in the string are the same.

A substring is a contiguous sequence of characters within the string.

Solution:

One approach to solve this problem is to iterate through the string and count the number of homogenous substrings at each index. We can do this by keeping track of the length of the current homogenous substring and multiplying it with the number of substrings that can be formed by adding the current character to the substring.

Let's consider an example to understand this approach better. Suppose the input string is "abbcccddddeeeee" and we start iterating from the first character.

• At the first character, we have a homogenous substring of length 1.
• At the second character, the substring is still homogenous since the character is the same as the previous one. So, we add the count of the new substring of length 2 to the count of the previous substring.
• At the third character, the substring is no longer homogenous since the character is different from the previous one. So, we start a new homogenous substring of length 1 and add it to the count.
• At the fourth character, the substring is still not homogenous since the character is different from the previous one. So, we start a new homogenous substring of length 1 and add it to the count.
• At the fifth character, we have a homogenous substring of length 5. We add the count of the new substring of length 5 to the count of the previous substring of length 1.
• We continue this process for the entire string and add up the counts of all the homogenous substrings at each index.

Here is the Python implementation of the above approach that runs in O(N) time complexity:

class Solution: def countHomogenous(self, s: str) -> int: curr_len = 1 count = 0 mod = 10**9 + 7 for i in range(1, len(s)): if s[i] == s[i-1]: curr_len += 1 else: count += (curr_len * (curr_len + 1) // 2) % mod curr_len = 1 count += (curr_len * (curr_len + 1) // 2) % mod return count % mod

In this implementation, we keep track of the length of the current homogenous substring in the curr_len variable. We also keep a count of all the homogenous substrings in the count variable.

At each index i, if the character at i is the same as the character at i-1, we increment the curr_len variable. Otherwise, we add the count of the current homogenous substring to the count variable using the formula (n * (n+1) // 2), where n is the length of the current homogenous substring.

Finally, we need to add the count of the last homogenous substring to the count variable before returning it.

The time complexity of this solution is O(N) since we iterate through the string only once. The space complexity is O(1) since we use constant space to store the variables.

1