Count Number of Homogenous Substrings

Problem 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.

Key Insights

• Homogenous substrings can be formed from consecutive identical characters.
• The number of homogenous substrings that can be formed from k consecutive identical characters is given by the formula k * (k + 1) / 2.
• We can iterate through the string and count the lengths of consecutive identical characters to calculate the total number of homogenous substrings.

Space and Time Complexity

Time Complexity: O(n) - We traverse the string once. Space Complexity: O(1) - We use a constant amount of space.

Solution

To solve the problem, we will use a simple iteration approach. We will keep track of the count of consecutive characters and whenever we encounter a different character, we will use the formula to calculate the number of homogenous substrings for the previous character sequence. We will accumulate the total count and return the result mod 10^9 + 7.

Code Solutions