Description
Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo $10^9 + 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.
Solution
Since we are counting the number of all homogenous substring, we do not need additional data structure to hold the number of each homogenous substring.
Given a string “aaa” and by iterating though this string:
- str[0], we could find a homogenous substr “a”.
- str[1], we could also find a homgenous substr “a” and “aa”.
- str[2], “a” “aa” “aaa”
Therefore, we could find that when the last character is the same as the current one, then we could find additional “number of repetitive characters” number of homogenous substring.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int countHomogenous(string s) {
int output = 0, cur = 0;
char last = 0;
for (auto c: s) {
if (c != last) {
last = c;
cur = 1;
}
else {
cur++;
}
output += cur;
output %= 1'000'000'007;
}
return output;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
pub fn count_homogenous(s: String) -> i32 {
let (mut output, mut cur) = (0, 0);
let mut last: char = '\0';
for c in s.chars() {
if c != last {
last = c;
cur = 1;
} else {
cur += 1;
}
output += cur;
output %= 1_000_000_007;
}
output
}
}