Count Number of Homogenous Substrings

LeetCode 1885 | Difficulty: Medium

Medium

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.

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 <= 10^5`

- `s` consists of lowercase letters.

Topics: Math, String

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 125 ms)

Metric	Value
Runtime	125 ms
Memory	39.3 MB
Date	2022-01-14

Solution

public class Solution {
    public int CountHomogenous(string s) {
        double result = 0;
        double mod = (1e9)+7;
        int n = s.Length;
        int i = 0;
        while(i<s.Length)
        {
            int j = i;
            double dp =0;
            double sum = 0;
            while(j<n && s[j] == s[i])
            {
                dp++;
                sum = (sum+dp)%mod;
                j++;
                
            }
            result = (result+sum)%mod;
            i = j;
        }
        
        return (int)result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: A string of only 'a's of length k contains k + 1 choose 2 homogenous substrings.

Hint 2: Split the string into substrings where each substring contains only one letter, and apply the formula on each substring's length.