Count Number of Homogenous Substrings — Medium Problem & Solution

Problem statement

A string is homogenous when all of its characters are the same.

Return the number of homogenous substrings of s, modulo 10⁹ + 7.

Example 1

Input: s = "codekairo"
Output: 9
Explanation: No two adjacent characters match, so only the nine single characters qualify.

Example 2

Input: s = "abbcccaa"
Output: 13
Explanation: 1 + 3 + 6 + 3 — each run of length `L` contributes `L(L+1)/2`.

Example 3

Input: s = "zzzzz"
Output: 15

Constraints

• 1 <= s.length <= 10^5
• s consists of lowercase letters.

How to solve Count Number of Homogenous Substrings

Count substrings by their right endpoint. At position i, the number of homogenous substrings ending there equals the length of the run of equal characters ending at i. Sum those, modulo 10⁹ + 7.

Approach

1. Keep run, reset to 1 whenever the character differs from the previous one, incremented otherwise.
2. Add run to a running total at every position, taking the modulo.

Why it works

Counting by right endpoint turns the run formula L(L+1)/2 into a single accumulation — you never have to find the run boundaries or multiply anything, and the total never exceeds the modulus between steps. The formula version is equivalent, but needs 64-bit arithmetic for L(L+1)/2 before the modulo when L is large.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• The result must be taken modulo 10⁹ + 7 — the raw count overflows 32 bits at the upper bound.
• run resets to 1, not 0, on a change of character.
• Single characters are homogenous substrings and must be counted.

Reference solution

Python

def countHomogenous(s: str) -> int:
    MOD = 10**9 + 7
    total = 0
    run = 0
    for i, c in enumerate(s):
        run = run + 1 if i > 0 and c == s[i - 1] else 1
        total = (total + run) % MOD
    return total

JavaScript

var countHomogenous = function(s) {
    var MOD = 1000000007;
    var total = 0, run = 0;
    for (var i = 0; i < s.length; i++) {
        run = i > 0 && s.charAt(i) === s.charAt(i - 1) ? run + 1 : 1;
        total = (total + run) % MOD;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Find the Winner of the Circular Game Medium
• Stone Game VII Medium
• Number of Ways to Divide a Long Corridor Medium
• Count Ways to Group Overlapping Ranges Medium
• Count Number of Ways to Place Houses Medium
• Count Number of Texts Medium