1759. Count Number of Homogenous Substrings
Explanation
To solve this problem, we can iterate through the input string s while keeping track of the current character and the count of consecutive occurrences of that character. For each character, we can calculate the number of homogenous substrings ending at that character. The total number of homogenous substrings will be the sum of these counts.
Algorithmic Idea
- Initialize variables
resultandcountto 0. - Iterate through the characters of the input string
s. - For each character:
- If it is the same as the previous character, increment the count.
- Otherwise, calculate the number of homogenous substrings ending at the current character using the formula
(count * (count + 1)) / 2. - Add this count to the result.
- After the loop, calculate the number of homogenous substrings for the last character using the same formula.
- Return the result modulo 10^9 + 7.
Time Complexity
The time complexity of this approach is O(n), where n is the length of the input string s.
Space Complexity
The space complexity of this approach is O(1) as we are using a constant amount of extra space.
class Solution {
public int countHomogenous(String s) {
int mod = 1000000007;
int result = 0;
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (i == 0 || s.charAt(i) == s.charAt(i - 1)) {
count++;
} else {
result = (result + count * (count + 1) / 2) % mod;
count = 1;
}
}
result = (result + count * (count + 1) / 2) % mod;
return result;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.