Count Number of Homogenous Substrings

Medium
1033.

Count Number of Homogenous Substrings

Count Number of Homogenous Substrings is a medium coding problem on strings and math, asked in Amazon, Google and Oracle interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var countHomogenous = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Number of Homogenous Substrings — Problem & Solution

Count Number of Homogenous Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Number of Homogenous Substrings is a medium coding problem on strings and math, asked in Amazon, Google and Oracle interviews.

  • Difficulty: Medium
  • Topics: Strings, Math
  • Asked at: Amazon, Google, Oracle
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Count Number of Homogenous Substrings

  1. Hint 1

    Every homogenous substring lies inside a maximal run of one repeated character.

  2. Hint 2

    A run of length L contains L * (L + 1) / 2 substrings.

  3. Hint 3

    Equivalently, sweep once and add the current run length at every position.

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

Java

public static int countHomogenous(String s) {
    final long MOD = 1000000007L;
    long total = 0;
    long run = 0;
    for (int i = 0; i < s.length(); i++) {
        run = (i > 0 && s.charAt(i) == s.charAt(i - 1)) ? run + 1 : 1;
        total = (total + run) % MOD;
    }
    return (int) total;
}

C++

int countHomogenous(string s) {
    const long long MOD = 1000000007LL;
    long long total = 0, run = 0;
    for (size_t i = 0; i < s.size(); i++) {
        run = (i > 0 && s[i] == s[i - 1]) ? run + 1 : 1;
        total = (total + run) % MOD;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings