Count Number of Homogenous Substrings

MEDIUM

Description

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.

Approaches

Checkout 2 different approaches to solve Count Number of Homogenous Substrings. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store the count and loop indices.

Pros and Cons

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).

Code Solutions

Checking out 4 solutions in different languages for Count Number of Homogenous Substrings. Click on different languages to view the code.

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 ; } }

Video Solution

Watch the video walkthrough for Count Number of Homogenous Substrings

Patterns:

Math

Data Structures:

String

Companies:

Virtu Financial |