Count Number of Homogenous Substrings

medium string counting math

Problem

A string is homogenous if all of its characters are the same. Given a string s, return the number of homogenous (contiguous) substrings of s. Because the count can be huge, return it modulo 10⁹ + 7.

Inputs = "abbcccaa"

Output13

The runs are a, bb, ccc, aa. A run of length L contributes L·(L+1)/2 substrings: 1 + 3 + 6 + 3 = 13.

Inputs = "zzzzz"

Output15

One run of length 5 gives 5·6/2 = 15 homogenous substrings.

s (lowercase letters)

def count_homogenous(s):
    MOD = 10**9 + 7
    total = 0
    run = 0
    prev = ""
    for ch in s:
        if ch == prev:
            run += 1
        else:
            run = 1
        total = (total + run) % MOD
        prev = ch
    return total

function countHomogenous(s) {
  const MOD = 1000000007;
  let total = 0;
  let run = 0;
  let prev = "";
  for (const ch of s) {
    if (ch === prev) run += 1;
    else run = 1;
    total = (total + run) % MOD;
    prev = ch;
  }
  return total;
}

int countHomogenous(String s) {
    final int MOD = 1000000007;
    long total = 0;
    long run = 0;
    char prev = 0;
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (ch == prev) run += 1;
        else run = 1;
        total = (total + run) % MOD;
        prev = ch;
    }
    return (int) total;
}

int countHomogenous(string s) {
    const long long MOD = 1000000007;
    long long total = 0;
    long long run = 0;
    char prev = 0;
    for (char ch : s) {
        if (ch == prev) run += 1;
        else run = 1;
        total = (total + run) % MOD;
        prev = ch;
    }
    return (int) total;
}

Explanation

Every homogenous substring lives entirely inside one run of equal characters. So the string splits into independent blocks like a | bb | ccc | aa, and we can count each block on its own.

A run of length L contains exactly L·(L+1)/2 homogenous substrings (length-1, length-2, …, length-L). The closed form is handy, but the cleanest single-pass trick is to add the current run length at every index.

We scan left to right, keeping run = how many equal characters end at the current position. If the character equals the previous one, run grows by 1; otherwise a new run starts and run resets to 1.

The number of homogenous substrings that end at the current index is exactly run (the single character, plus every longer suffix of the current run). Summing run over all positions therefore counts every homogenous substring exactly once: 1 + (1+2) + (1+2+3) + (1+2) = 13 for "abbcccaa".

Because the total may overflow, we keep it modulo 10⁹ + 7. The whole thing is one linear pass with O(1) extra memory.

Time: O(n) Space: O(1)