Is Count Number of Homogenous Substrings easy or hard?

The problem is classified as Medium on LeetCode. The challenge lies in recognizing that consecutive character runs generate multiple substrings and deriving an efficient counting method instead of enumerating all substrings.

Count Number of Homogenous Substrings Python/Java solution

Both Python and Java implementations follow the same idea: scan the string, track the current run length, and add it to the result. Apply modulo 1e9+7 after each update. The algorithm remains O(n) time and O(1) space regardless of language.

How to solve Count Number of Homogenous Substrings in O(n)?

Iterate through the string while keeping a counter of consecutive identical characters. If the current character matches the previous one, increase the counter; otherwise reset it to 1. Add the counter value to the total for every position. Apply modulo 1e9+7 to prevent overflow.

What is the best approach for Count Number of Homogenous Substrings?

The optimal approach uses a run-length or two-pointer scan of the string. Track the length of consecutive identical characters and add the run length to the result at every step. This counts all homogenous substrings ending at the current index. The solution runs in O(n) time with O(1) space.

Is Count Number of Homogenous Substrings asked at Google/Amazon/Meta?

This problem represents a common string run-length counting pattern frequently used in interviews at large tech companies such as Amazon, Google, and Meta. Variants appear in substring counting or consecutive-character problems where candidates must derive counts from runs.

What data structure is used in Count Number of Homogenous Substrings?

No complex data structure is required. The solution mainly uses simple variables to track the length of consecutive characters while iterating through a string. The key concept is run-length counting combined with arithmetic accumulation.

What is the time complexity of Count Number of Homogenous Substrings?

The optimal algorithms run in O(n) time where n is the length of the string. Each character is processed exactly once while maintaining a counter for consecutive characters. Space complexity remains O(1) because only a few integer variables are used.

Description Hints 2 Solution Video 12:46

1759. Count Number of Homogenous Substrings

Medium57.6% acceptance2 companies

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 10⁹ + 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⁵
s consists of lowercase letters.

Asked at 2 companies

Virtu Financial

Google

Topics

Math String

Hints open one at a time

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.

12:46

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution