# Count Number of Homogenous Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-number-of-homogenous-substrings)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-homogenous-substrings
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
**Companies:** [Virtu Financial](https://scaleengineer.com/companies/virtu-financial)
---
## 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 <= 105`
* `s` consists of lowercase letters.

# Approaches
## Brute Force with Nested Loops
This approach involves generating all possible substrings of the input string `s` and checking if each substring is homogenous. A substring is homogenous if all its characters are identical. We can use two nested loops to define the start and end points of each substring.
**Time:** O(N^2), where N is the length of the string. In the worst-case scenario (e.g., a string like "aaaaa"), the inner loop runs N times for each iteration of the outer loop. · **Space:** O(1), as we only use a few variables to store the count and loop indices.
**Pros:** Relatively straightforward to understand and implement.; Doesn't require complex data structures.
**Cons:** Inefficient for large inputs. It will result in a "Time Limit Exceeded" error for the given constraints (N up to 10^5).
### Explanation
We iterate through the string with an outer loop using index `i` from 0 to `n-1`, where `n` is the length of the string. The index `i` represents the starting position of a potential homogenous substring.
For each `i`, we start an inner loop with index `j` from `i` to `n-1`.
The substring from `i` to `j` is homogenous if `s.charAt(j)` is the same as `s.charAt(i)`.
If they are the same, we have found one homogenous substring, so we increment our total count.
If `s.charAt(j)` is different from `s.charAt(i)`, it means the substring `s.substring(i, j+1)` is not homogenous. Furthermore, any longer substring starting at `i` will also not be homogenous. Therefore, we can break the inner loop and continue with the next starting position `i+1`.
We keep a running total of the count, applying the modulo operation at each addition to prevent integer overflow.
The final count is the answer.
```java
class Solution {
    public int countHomogenous(String s) {
        int n = s.length();
        long totalCount = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (s.charAt(j) == s.charAt(i)) {
                    totalCount = (totalCount + 1) % MOD;
                } else {
                    break;
                }
            }
        }

        return (int) totalCount;
    }
}
```
### Algorithm
- Initialize `totalCount = 0` and `MOD = 1_000_000_007`.
- Iterate through the string with an index `i` from `0` to `length - 1`.
- For each `i`, start an inner loop with an index `j` from `i` to `length - 1`.
- Check if the character at `j` is the same as the character at `i`.
- If they are the same, it means the substring from `i` to `j` is homogenous. Increment `totalCount` and apply modulo.
- If they are different, break the inner loop, as any further substring starting at `i` will not be homogenous.
- After the loops complete, return `totalCount`.

## Single Pass Iteration
A more efficient approach is to iterate through the string just once. We can count the lengths of consecutive blocks of identical characters. For a block of `k` identical characters, it contributes `k * (k + 1) / 2` homogenous substrings. However, a simpler way to achieve the same result is to maintain a `streak` counter.
**Time:** O(N), where N is the length of the string. We perform a single pass through the string. · **Space:** O(1), as we only use a constant amount of extra space for variables like `ans` and `currentStreak`.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for the given constraints.; Low memory usage.
**Cons:** The logic of adding the streak count might be slightly less intuitive than the brute-force method initially.
### Explanation
We iterate through the string from left to right, keeping track of the length of the current consecutive streak of identical characters.
Let's use a variable `streak` to store this length.
We initialize a result variable `ans` to 0.
For each character `s.charAt(i)`, we compare it with the previous character `s.charAt(i-1)`.
If `i > 0` and `s.charAt(i)` is the same as `s.charAt(i-1)`, it means the streak continues. We increment `streak`.
If it's the first character (`i == 0`) or if `s.charAt(i)` is different from `s.charAt(i-1)`, the streak is broken, and a new one starts. We reset `streak` to 1.
In each step of the iteration, we add the current `streak` value to our total `ans`. Why does this work? When we have a streak of length `k`, we are adding `k` to the total. This is because the new character forms `k` new homogenous substrings: one of length 1 (itself), and `k-1` substrings by appending itself to the `k-1` homogenous substrings ending at the previous position.
For example, for "aaa":
- 'a': streak=1, ans=1. (Substrings: "a")
- 'aa': streak=2, ans=1+2=3. (New substrings: "a", "aa". Total: "a", "a", "aa")
- 'aaa': streak=3, ans=3+3=6. (New substrings: "a", "aa", "aaa". Total: "a", "a", "a", "aa", "aa", "aaa")
The sum of streaks `1 + 2 + ... + k` is exactly `k * (k + 1) / 2`, which is the number of homogenous substrings in a block of length `k`.
We must perform the addition modulo `10^9 + 7` to prevent overflow.
```java
class Solution {
    public int countHomogenous(String s) {
        int MOD = 1_000_000_007;
        long ans = 0;
        int currentStreak = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (i == 0 || s.charAt(i) == s.charAt(i - 1)) {
                currentStreak++;
            } else {
                currentStreak = 1;
            }
            ans = (ans + currentStreak) % MOD;
        }
        
        return (int) ans;
    }
}
```
### Algorithm
- Initialize `ans = 0`, `currentStreak = 0`, and `MOD = 1_000_000_007`.
- Iterate through the string `s` with an index `i` from `0` to `length - 1`.
- Inside the loop, check if it's the first character (`i == 0`) or if the current character `s.charAt(i)` is the same as the previous character `s.charAt(i - 1)`.
- If they are the same, increment `currentStreak`.
- If they are different, a new homogenous block has started, so reset `currentStreak` to `1`.
- Add the `currentStreak` to `ans` and take the result modulo `MOD`.
- After the loop finishes, `ans` will hold the total count of homogenous substrings. Return `ans`.

# Solutions
### CSharp

```csharp
public class Solution { public int CountHomogenous ( string s ) { long MOD = 1000000007 ; long ans = 0 ; for ( int i = 0 , j = 0 ; i < s . Length ; i = j ) { j = i ; while ( j < s . Length && s [ j ] == s [ i ]) { ++ j ; } int cnt = j - i ; ans += ( long ) ( 1 + cnt ) * cnt / 2 ; ans %= MOD ; } return ( int ) ans ; } }
```

### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int countHomogenous(string s) {
    int n = s.size();
    long ans = 0;
    for (int i = 0, j = 0; i < n; i = j) {
      j = i;
      while (j < n && s[j] == s[i])
        ++j;
      int cnt = j - i;
      ans += 1ll * (1 + cnt) * cnt / 2;
      ans %= mod;
    }
    return ans;
  }
};

```

### Python

```python
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

```