Leetcode 1759: Count Number of Homogenous Substrings

Input: The input consists of a string `s` made up of lowercase alphabetic characters.

Example: Input: s = 'aabbbcc'

Constraints:

• 1 <= s.length <= 10^5

• s consists only of lowercase English letters.

Output: Return the total number of homogenous substrings modulo 10^9 + 7.

Example: Output: 10

Constraints:

• The result should be modulo 10^9 + 7.

Goal: The goal is to efficiently count the number of homogenous substrings in the given string `s`.

Steps:

• 1. Traverse the string and identify consecutive characters that are the same.

• 2. For each sequence of `k` consecutive identical characters, the number of homogenous substrings is the sum of the first `k` integers, which is `k * (k + 1) / 2`.

• 3. Accumulate this count for each sequence of homogenous characters found in the string.

• 4. Return the total number of substrings modulo 10^9 + 7.

Goal: Make sure the solution handles large inputs efficiently.

Steps:

• The solution must work efficiently for strings of length up to 10^5.

Assumptions:

• The string `s` is not empty and consists only of lowercase letters.

• Input: Input: s = 'aabbbcc'

• Explanation: The homogenous substrings are 'a', 'a', 'b', 'b', 'b', 'bb', 'bbb', 'c', 'c', and 'cc'. Total: 10.

• Input: Input: s = 'abc'

• Explanation: The homogenous substrings are 'a', 'b', and 'c'. Total: 3.

Approach: The approach involves traversing the string, identifying consecutive identical characters, and counting the number of homogenous substrings using the sum of the first `k` integers formula.

Observations:

• The number of homogenous substrings for a group of `k` consecutive characters is the sum of the first `k` integers.

• We need to identify sequences of consecutive identical characters and compute the number of homogenous substrings for each sequence.

Steps:

• 1. Initialize a variable to keep track of the total count of homogenous substrings.

• 2. Loop through the string and find segments of consecutive characters that are the same.

• 3. For each segment of length `k`, add `k * (k + 1) / 2` to the total count.

• 4. Return the result modulo 10^9 + 7.

Empty Inputs:

• If the input string is empty, return 0.

Large Inputs:

• For very large inputs, ensure the solution runs in linear time, O(n), where n is the length of the string.

Special Values:

• If all characters are the same, the count of homogenous substrings will be the sum of the first `n` integers.

Constraints:

• The solution should handle strings of length up to 10^5 efficiently.

int countHomogenous(string s) {
    long long j = 0, cnt = 0, n = s.size();
    int mod = (int) 1e9 + 7;
    
    for(int i = 0; i < n; i++) {
        if(s[j] == s[i]) continue;
        else {
            long long len = i - j;
            cnt += len * (len + 1) / 2;
            j = i;                
        }
    }
    long long len = n - j;
    cnt += len * (len + 1) / 2; 
    return cnt % mod;
}

1 : Function Declaration

int countHomogenous(string s) {

Declares the function to count contiguous substrings with identical characters.

2 : Variable Initialization

    long long j = 0, cnt = 0, n = s.size();

Initializes variables to track the start of a segment, the total count, and the length of the string.

3 : Constant Initialization

    int mod = (int) 1e9 + 7;

Defines a modulo constant to prevent overflow in the result.

4 : Loop

    for(int i = 0; i < n; i++) {

Iterates through the string to identify homogenous segments.

5 : Condition Check

        if(s[j] == s[i]) continue;

Checks if the current character is part of the ongoing homogenous segment.

6 : Condition Else Block

        else {

Handles the case when a new segment starts.

7 : Segment Length Calculation

            long long len = i - j;

Calculates the length of the completed homogenous segment.

8 : Count Update

            cnt += len * (len + 1) / 2;

Updates the total count by adding the number of substrings for the segment.

9 : Index Update

            j = i;

Moves the segment start index to the current character.

10 : Final Segment Length Calculation

    long long len = n - j;

Calculates the length of the final homogenous segment.

11 : Final Count Update

    cnt += len * (len + 1) / 2;

Adds the substrings count for the last segment to the total.

12 : Return Statement

    return cnt % mod;

Returns the result modulo the defined constant to ensure it fits within standard bounds.

Best Case: O(n), where n is the length of the string.

Average Case: O(n), as each character is checked once.

Worst Case: O(n), where n is the length of the string.

Description: The time complexity is linear because we only traverse the string once.

Best Case: O(1), as the space used is constant.

Worst Case: O(1), since no extra space is needed except for counters.

Description: The space complexity is constant, O(1), since only a few variables are used for counting.

Leetcode 1759: Count Number of Homogenous Substrings

Explore →