Watch 10 video solutions for Count Number of Homogenous Substrings, a medium level problem involving Math, String. This walkthrough by codestorywithMIK has 7,722 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 109 + 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 <= 105s consists of lowercase letters.Problem Overview: Given a string s, count how many substrings consist of only one repeating character. A substring like "aaa" contributes multiple homogenous substrings: a, a, a, aa, aa, and aaa. The result must be returned modulo 1e9 + 7.
Approach 1: Two-Pointer Approach (O(n) time, O(1) space)
Traverse the string while tracking the length of the current run of identical characters. Use two pointers or a single index with a counter. When the current character matches the previous one, extend the run; otherwise reset the run length to 1. Each extension adds the current run length to the total count because every new character forms additional homogenous substrings ending at that index. This works because a run of length k contributes exactly k substrings ending at the current position.
This approach relies on simple iteration and constant memory, making it ideal for large inputs. The algorithm scans the string once, updates a running count, and applies the modulo constraint after each addition. It’s a common pattern when solving run-length problems on string data.
Approach 2: Mathematical Counting Approach (O(n) time, O(1) space)
Instead of counting substrings incrementally, group consecutive identical characters and compute their contribution using a formula. If a run of the same character has length k, the number of homogenous substrings inside that run equals k * (k + 1) / 2. Iterate through the string, measure each run length, apply the formula, and add the result to the answer.
This method separates the counting logic from traversal and emphasizes the combinatorial insight behind the problem. It is effectively run-length encoding combined with a simple math formula. The runtime remains linear because each character is processed once, and only a few integer variables are maintained.
Recommended for interviews: The two-pointer method is usually the expected solution because it demonstrates strong control over iteration and incremental counting in two-pointer style scanning. The mathematical approach shows deeper understanding of how substring counts arise from run lengths, which can make the reasoning clearer. Both run in O(n) time with O(1) space and are considered optimal.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Run-Length Counting | O(n) | O(1) | Best general solution. Single pass with incremental counting, common interview pattern. |
| Mathematical Run-Length Formula | O(n) | O(1) | When you prefer grouping characters first and computing substrings using the k*(k+1)/2 formula. |