LeetCode Solutions Blog

Count Number of Homogenous Substrings

Number: 1885

Difficulty: Medium

Paid? No

Problem Description

Given a string s, count the number of homogenous substrings in s. A homogenous substring is defined as a substring where all characters are identical. Since the answer can be very large, return it modulo 10^9 + 7.

Key Insights

A contiguous block (run) of identical characters of length n contributes n*(n+1)/2 homogenous substrings.
Simply iterating through the string and counting the length of consecutive identical characters can give us each run length.
Use modulo arithmetic at each step to handle large numbers.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), as only a few additional variables are used.

Solution

The solution iterates over the string while maintaining a counter for the length of the current run of identical characters. When the character changes, it calculates the number of homogenous substrings from the run using the arithmetic series formula (n*(n+1)/2) and adds it to a running total. The modulo operation is applied to keep the result within the required range. This method efficiently calculates the total count by processing the string in a single pass.

Code Solutions

# Define the modulo constant
MOD = 10**9 + 7

def countHomogenous(s: str) -> int:
    total_count = 0       # To store the total number of homogenous substrings
    current_run = 1       # Count of consecutive identical characters
    
    # Loop through the string starting from the second character
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            # Increase the run count if the current character matches the previous one
            current_run += 1
        else:
            # Add the number of substrings from the current run and reset the run count
            total_count = (total_count + (current_run * (current_run + 1) // 2)) % MOD
            current_run = 1  # Reset for the new character run
            
    # Add substrings count from the last run
    total_count = (total_count + (current_run * (current_run + 1) // 2)) % MOD
    return total_count

# Example usage:
s = "abbcccaa"
print(countHomogenous(s))  # Expected output: 13