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 <= 105s consists of lowercase letters.In this approach, we make use of two pointers to keep track of the start and end of a sequence of identical characters. As we iterate through the string, we update the end pointer when we find the same character, and on encountering a different character, we calculate the number of homogenous substrings formed using the formula for the sum of first n natural numbers: n * (n + 1) / 2, where n is the length of the sequence of identical characters. We repeat this process for each identified sequence and accumulate the total number of homogenous substrings.
In the C solution, we iterate through the string while maintaining the length of consecutive identical characters with the length variable. When a different character is encountered, we add the number of homogenous substrings formed by the previous sequence to count. The final count is taken modulo 10^9 + 7 as required.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we only use a constant amount of extra space.
This approach involves counting the sequences of homogenous substrings by leveraging arithmetic progression's sum. By identifying the start and end of each homogenous substring part, we can determine the total count for those characters. We iterate through the string, find the size of each segment, and calculate total substrings using the arithmetic formula.
The C code initializes a result variable and iterates through the string to compute lengths of continuous characters. The formula for an arithmetic progression then calculates homogenous substrings from each segment.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(1) since no extra space is used apart from fixed variables.
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n), where n is the length of the string. |
| Mathematical Counting Approach | Time Complexity: O(n) where n is the length of the string. |
Count Number of Homogenous Substrings | Intuition | Math | Leetcode - 1759 • codestorywithMIK • 5,251 views views
Watch 9 more video solutions →Practice Count Number of Homogenous Substrings with our built-in code editor and test cases.
Practice on FleetCode