Count Number of Homogenous Substrings

Problem Statement

In this problem, we are given a string s and are tasked with counting the number of its homogenous substrings. A homogenous substring is defined as a sequence of characters where all characters are the same. Each contiguous substring that fits this definition should be counted. The solution's result must be returned as a modulo 10^9 + 7, to handle potentially large numbers due to the constraints on the string length.

Exploring the definition through examples:

• For a string "aaa", the homogenous substrings include "a", "a", "a", "aa", "aa", and "aaa". Each individual occurrence of a character as well as each possible contiguous grouping of identical characters should be considered.

Given the constraints, where the length can be as large as 100,000 and only lowercase letters are involved, efficient string processing is critical to manage potential time complexities.

Examples

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.

Example 2

Input:

s = "xy"

Output:

2

Explanation:

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

Example 3

Input:

s = "zzzzz"

Output:

15

Constraints

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

Approach and Intuition

The task is to identify all contiguous blocks of the same characters and determine the count of all possible substrings within these blocks.

Steps to Solve:

1. Traverse through the string s using a pointer or index.

2. Start by identifying the beginning of a homogenous block. This is easily spotted when the current character does not match the previous character (or if we are at the start of the string).

3. Maintain a count of how many times the same character appears consecutively. Let’s call this length L for any block.

4. Using the property that a single character can form 1 substring, two consecutive characters can form 1 + 2 = 3 substrings, and so on, the total number of substrings for a homogenous block of length L can be computed using the formula L * (L + 1) / 2.

5. As you detect the end of a homogenous block (either when s[i] is not equal to s[i-1] or the string has ended), compute and add the result of L * (L + 1) / 2 to the total count of substrings.

6. Be sure to include the result modulo 10^9 + 7 at each addition to keep numbers manageable and handle the overflow.

Example Analysis:

• For s = "abbcccaa", the sequence of operations will be:
  • Find 'a'; length is 1, yielding 1 substring.
  • Find 'bb'; length is 2, yielding 2*(2+1)/2 = 3 substrings.
  • And so forth, until the end of the string.

This approach minimizes the need to store or directly count each seen substring, instead leveraging mathematical properties to efficiently compute required values based on identified patterns in the data, adhering well to the problem’s constraints.

Solutions

class Solution {
public:
    int countContiguous(string str) {
        int total = 0;
        int streak = 0;
        int CONST_MOD = 1000000007;
            
        for (int index = 0; index < str.length(); index++) {
            if (index == 0 || str[index] == str[index - 1]) {
                streak++;
            } else {
                streak = 1;
            }
                
            total = (total + streak) % CONST_MOD;
        }
            
        return total;
    }
};