Count Number of Homogenous Substrings solution and explanation
Google
9 more videos on this problem
Count Number of Homogenous Substrings | Intuition | Math | Leetcode - 1759codestorywithMIK · 12:46 · 8K views
1759. Count Number of Homogenous Substrings | 3 waysAryan Mittal · 13:20 · 2K views
LeetCode 1759. Count Number of Homogenous Substrings | Weekly Contest 228 | Algorithm Explained C++Cherry Coding [IIT-G] · 7:29 · 1K views
1759. Count Number of Homogenous Substrings | Weekly contest 228 | Leetcode | Hindi | C++Leetforces · 4:58 · 1K views
1759. Count Number of Homogenous Substrings (Leetcode Medium)Programming Live with Larry · 6:56 · 830 views
Count Number of Homogenous Substrings (Leetcode 1759)Coding Interviews · 16:23 · 402 views
Daily Leetcode #1318 part 2: Nov 09, 2023 - 1759. Count Number of Homogenous SubstringsProgramming Live with Larry · 11:26 · 262 views
Solving LeetCode 1759 Count Number of Homogenous Substrings | Math | Easy to UnderstandCode Harmony · 12:57 · 210 views
Code EveryDay | Math, String | Asked in: Flipkart | 1759 Count Number of Homogenous SubstringsProgramming Pathshala · 14:06 · 139 views
Leetcode 1759. Count Number of Homogenous Substrings (list groups)LetsCode · 6:18 · 136 views
The problem
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 <= 105sconsists of lowercase letters.
Approach overview
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 1: Two-Pointer Approach
In this approach, we make use of two pointers to keep track of the start and end of a sequence of identical characters. As we iterate through the string, we update the end pointer when we find the same character, and on encountering a different character, we calculate the number of homogenous substrings formed using the formula for the sum of first n natural numbers: n * (n + 1) / 2, where n is the length of the sequence of identical characters. We repeat this process for each identified sequence and accumulate the total number of homogenous substrings.
class Solution:
MOD = 1000000007
def countHomogenous(self, s: str) -> int:
count = 0
length = 1
for i in range(1, len(s)):
if s[i] == s[i - 1]:
length += 1
else:
count = (count + length * (length + 1) // 2) % self.MOD
length = 1
count = (count + length * (length + 1) // 2) % self.MOD
return count
# Example usage
sol = Solution()
print(sol.countHomogenous("abbcccaa"))class Solution {
private static final int MOD = 1000000007;
public int countHomogenous(String s) {
long count = 0;
int length = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) {
length++;
} else {
count = (count + (long) length * (length + 1) / 2) % MOD;
length = 1;
}
}
count = (count + (long) length * (length + 1) / 2) % MOD;
return (int) count;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.countHomogenous("abbcccaa"));
}
}#include <iostream>
#include <string>
#define MOD 1000000007
using namespace std;
int countHomogenous(string s) {
long count = 0;
int length = 1;
for (size_t i = 1; i < s.length(); ++i) {
if (s[i] == s[i - 1]) {
length++;
} else {
count = (count + (long)length * (length + 1) / 2) % MOD;
length = 1;
}
}
count = (count + (long)length * (length + 1) / 2) % MOD;
return (int)count;
}
int main() {
cout << countHomogenous("abbcccaa") << endl;
return 0;
}function countHomogenous(s) {
const MOD = 1000000007;
let count = 0;
let length = 1;
for (let i = 1; i < s.length; i++) {
if (s[i] === s[i - 1]) {
length++;
} else {
count = (count + length * (length + 1) / 2) % MOD;
length = 1;
}
}
count = (count + length * (length + 1) / 2) % MOD;
return count;
}
console.log(countHomogenous("abbcccaa"));#include <stdio.h>
#define MOD 1000000007
int countHomogenous(char* s) {
long count = 0;
int length = 1;
for (int i = 1; s[i] != '\0'; ++i) {
if (s[i] == s[i - 1]) {
length++;
} else {
count = (count + (long)length * (length + 1) / 2) % MOD;
length = 1;
}
}
count = (count + (long)length * (length + 1) / 2) % MOD;
return (int)count;
}
int main() {
char s[] = "abbcccaa";
printf("%d\n", countHomogenous(s));
return 0;
}using System;
public class Solution {
const int MOD = 1000000007;
public int CountHomogenous(string s) {
long count = 0;
int length = 1;
for (int i = 1; i < s.Length; i++) {
if (s[i] == s[i - 1]) {
length++;
} else {
count = (count + (long)length * (length + 1) / 2) % MOD;
length = 1;
}
}
count = (count + (long)length * (length + 1) / 2) % MOD;
return (int)count;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.CountHomogenous("abbcccaa"));
}
}In Python, the approach relies on iterating over the string and aggregating the count of homogenous substrings every time a change occurs in the character sequence using Python's // for integer division.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Mathematical Counting Approach
This approach involves counting the sequences of homogenous substrings by leveraging arithmetic progression's sum. By identifying the start and end of each homogenous substring part, we can determine the total count for those characters. We iterate through the string, find the size of each segment, and calculate total substrings using the arithmetic formula.
class Solution:
MOD = 1000000007
def countHomogenous(self, s: str) -> int:
result, length = 0, 1
for i in range(1, len(s)):
if s[i] == s[i - 1]:
length += 1
else:
result = (result + length * (length + 1) // 2) % self.MOD
length = 1
result = (result + length * (length + 1) // 2) % self.MOD
return result
# Example usage
sol = Solution()
print(sol.countHomogenous("abbcccaa"))class Solution {
private static final int MOD = 1000000007;
public int countHomogenous(String s) {
long result = 0;
int len = 1;
for (int i = 1; i < s.length(); ++i) {
if (s.charAt(i) == s.charAt(i - 1)) {
++len;
} else {
result = (result + (long) len * (len + 1) / 2) % MOD;
len = 1;
}
}
result = (result + (long) len * (len + 1) / 2) % MOD;
return (int) result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.countHomogenous("abbcccaa"));
}
}#include <iostream>
#include <string>
#define MOD 1000000007
using namespace std;
int countHomogenous(string s) {
long result = 0;
int len = 1;
for (size_t i = 1; i < s.size(); ++i) {
if (s[i] == s[i - 1]) {
++len;
} else {
result = (result + static_cast<long>(len) * (len + 1) / 2) % MOD;
len = 1;
}
}
result = (result + static_cast<long>(len) * (len + 1) / 2) % MOD;
return (int) result;
}
int main() {
cout << countHomogenous("abbcccaa") << endl;
return 0;
}function countHomogenous(s) {
const MOD = 1000000007;
let result = 0;
let length = 1;
for (let i = 1; i < s.length; ++i) {
if (s[i] === s[i - 1]) {
++length;
} else {
result = (result + length * (length + 1) / 2) % MOD;
length = 1;
}
}
result = (result + length * (length + 1) / 2) % MOD;
return result;
}
console.log(countHomogenous("abbcccaa"));#include <stdio.h>
#define MOD 1000000007
int countHomogenous(char* s) {
long result = 0;
int len = 1;
for (int i = 1; s[i]; ++i) {
if (s[i] == s[i - 1]) {
++len;
} else {
result = (result + (long)len * (len + 1) / 2) % MOD;
len = 1;
}
}
result = (result + (long)len * (len + 1) / 2) % MOD;
return (int) result;
}
int main(void) {
char s[] = "abbcccaa";
printf("%d\n", countHomogenous(s));
return 0;
}using System;
public class Solution {
const int MOD = 1000000007;
public int CountHomogenous(string s) {
long result = 0;
int len = 1;
for (int i = 1; i < s.Length; ++i) {
if (s[i] == s[i - 1]) {
++len;
} else {
result = (result + (long)len * (len + 1) / 2) % MOD;
len = 1;
}
}
result = (result + (long)len * (len + 1) / 2) % MOD;
return (int)result;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.CountHomogenous("abbcccaa"));
}
}With Python, sequence checks and evaluations are executed with the arithmetic sum processes applied using integer division to ensure smooth completion of homogenous substring counts.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Default Approach
function countHomogenous(s: string): number {
const mod = 1e9 + 7;
const n = s.length;
let ans = 0;
for (let i = 0, j = 0; j < n; j++) {
if (s[i] !== s[j]) {
i = j;
}
ans = (ans + j - i + 1) % mod;
}
return ans;
}func countHomogenous(s string) (ans int) {
n := len(s)
const mod int = 1e9 + 7
for i, j := 0, 0; i < n; i = j {
j = i
for j < n && s[j] == s[i] {
j++
}
cnt := j - i
ans += (1 + cnt) * cnt / 2
ans %= mod
}
return
}impl Solution {
pub fn count_homogenous(s: String) -> i32 {
const MOD: usize = (1e9 as usize) + 7;
let s = s.as_bytes();
let n = s.len();
let mut ans = 0;
let mut i = 0;
for j in 0..n {
if s[i] != s[j] {
i = j;
}
ans = (ans + j - i + 1) % MOD;
}
ans as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n) |
| Mathematical Counting Approach | Time Complexity: O(n) |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
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.