Count Number of Homogenous Substrings

Introduction:

Given a string s, the goal is to determine the number of homogenous substrings it contains. A string is considered homogenous if all its characters are the same. Substrings, on the other hand, are contiguous sequences of characters within a string. To handle potentially large results, the answer is returned modulo 10^9 + 7.

Problem Statement:

We are given a string s, and we need to count the number of homogenous substrings in it.

Example 1:

Input: "abbcccaa"
Output: 13

Explanation: The homogenous substrings are: "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). The total count is 3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

Example 2:

Input: "xy"
Output: 2

Explanation: The homogenous substrings are "x" and "y."

Example 3:

Input: "zzzzz"
Output: 15

Explanation: The string consists of five consecutive "z" characters. There are 15 substrings consisting of a single "z" character.

Constraints:

- 1 <= s.length <= 105
- s consists of lowercase letters.

Approach:

To count the number of homogenous substrings in the given string efficiently, we can use a simple loop. We iterate through the string, maintaining a count of consecutive characters that are the same. When we encounter a different character, we calculate the number of homogenous substrings that can be formed using the previous character and add it to the total count.

Pseudocode:

1. Initialize count = 0 and length = 1.
2.  Iterate through the string s from the second character (index 1) to the last character (index n-1).
3. If the current character is the same as the previous character, increment length.
4.  If the current character is different, calculate the number of homogenous substrings using the previous character: (length * (length + 1)) / 2, and add it to count.
5. After the loop, add the count of homogenous substrings for the last character.
6. Return count modulo 10^9 + 7.

Code :

#include <stdio.h>

int countHomogenous(char *s) {
    int mod = 1000000007;
    long count = 0;
    int length = 1;

    for (int i = 1; s[i] != '\0'; i++) {
        if (s[i] == s[i - 1]) {
            length++;
        } else {
            // Add the count of homogenous substrings of the previous character to the total count.
            count = (count + (long) length * (length + 1) / 2) % mod;
            length = 1;
        }
    }

    // Add the count of homogenous substrings for the last character.
    count = (count + (long) length * (length + 1) / 2) % mod;

    return (int) count;
}

int main() {
    char s[] = "abbcccaa";
    int result = countHomogenous(s);
    printf("Output: %d\n", result);

    return 0;
}

Output: 13

#include <iostream>
#include <string>

using namespace std;

int countHomogenous(string s) {
    int mod = 1000000007;
    long long count = 0;
    int length = 1;

    for (int i = 1; i < s.length(); i++) {
        if (s[i] == s[i - 1]) {
            length++;
        } else {
            // Add the count of homogenous substrings of the previous character to the total count.
            count = (count + (long long)length * (length + 1) / 2) % mod;
            length = 1;
        }
    }

    // Add the count of homogenous substrings for the last character.
    count = (count + (long long)length * (length + 1) / 2) % mod;

    return static_cast<int>(count);
}

int main() {
    string s = "abbcccaa";
    int result = countHomogenous(s);
    cout << "Output: " << result << endl;

    return 0;
}

Output: 13

public class Solution {
    public static int countHomogenous(String s) {
        int mod = 1000000007;
        long count = 0;
        int length = 1;

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                length++;
            } else {
                // Add the count of homogenous substrings of the previous character to the total count.
                count = (count + (long) length * (length + 1) / 2) % mod;
                length = 1;
            }
        }

        // Add the count of homogenous substrings for the last character.
        count = (count + (long) length * (length + 1) / 2) % mod;

        return (int) count;
    }

    public static void main(String[] args) {
        String s = "abbcccaa";
        int result = countHomogenous(s);
        System.out.println("Output: " + result);
    }
}

Output: 13

def count_homogenous(s):
    mod = 1000000007
    count = 0
    length = 1

    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            length += 1
        else:
            # Add the count of homogenous substrings of the previous character to the total count.
            count = (count + length * (length + 1) // 2) % mod
            length = 1

    # Add the count of homogenous substrings for the last character.
    count = (count + length * (length + 1) // 2) % mod

    return int(count)

# Example usage
s = "abbcccaa"
result = count_homogenous(s)
print("Output:", result)

Output: 13

<?php
function countHomogenous($s) {
    $mod = 1000000007;
    $count = 0;
    $length = 1;

    for ($i = 1; $i < strlen($s); $i++) {
        if ($s[$i] == $s[$i - 1]) {
            $length++;
        } else {
            // Add the count of homogenous substrings of the previous character to the total count.
            $count = ($count + $length * ($length + 1) / 2) % $mod;
            $length = 1;
        }
    }

    // Add the count of homogenous substrings for the last character.
    $count = ($count + $length * ($length + 1) / 2) % $mod;

    return (int)$count;
}

// Example usage
$s = "abbcccaa";
$result = countHomogenous($s);
echo "Output: " . $result . "\n";
?>

Output: 13

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input string s. We iterate through the string once, and the operations within the loop are constant time.

Space Complexity:

The space complexity of this solution is O(1) as we only use a constant amount of extra space for variables.

Conclusion:

Counting homogenous substrings in a string is a common problem that can be efficiently solved with a simple algorithm. This solution works well for strings of varying lengths and provides results modulo 10^9 + 7 to handle potentially large counts.