Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
"abbcccaa"
"xy"
"zzzzz"
consecutive-characters)number-of-substrings-with-only-1s)sum-of-subarray-ranges)count-the-number-of-good-subarrays)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1759: Count Number of Homogenous Substrings
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countHomogenous(String s) {
int n = s.length();
long ans = 0;
for (int i = 0, j = 0; i < n; i = j) {
j = i;
while (j < n && s.charAt(j) == s.charAt(i)) {
++j;
}
int cnt = j - i;
ans += (long) (1 + cnt) * cnt / 2;
ans %= MOD;
}
return (int) ans;
}
}
// Accepted solution for LeetCode #1759: Count Number of Homogenous Substrings
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
}
# Accepted solution for LeetCode #1759: Count Number of Homogenous Substrings
class Solution:
def countHomogenous(self, s: str) -> int:
mod = 10**9 + 7
i, n = 0, len(s)
ans = 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
cnt = j - i
ans += (1 + cnt) * cnt // 2
ans %= mod
i = j
return ans
// Accepted solution for LeetCode #1759: Count Number of Homogenous Substrings
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
}
}
// Accepted solution for LeetCode #1759: Count Number of Homogenous Substrings
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;
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.