# Count Number of Homogenous Substrings

#### Cyber Security : Go from Zero to Hero

Most Popular

60 Lectures 5.5 hours

#### Master C and Embedded C Programming- Learn as you go

Best Seller

66 Lectures 5.5 hours

#### C Programming from scratch- Master C Programming

Best Seller

60 Lectures 8 hours

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

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

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

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

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

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.