字符串 s ,返回 s 中 同构子字符串 的数目。由于答案可能很大,只需返回对 109 + 7 取余 后的结果(n<=1e5)。
思路:对于xxxffffxxx,同构字符串f有多少个?设n=len(ffff)
n个f
n-1个ff
n-2个fff
n-3个ffff
=1+2+3+4个同构字符串,规律就是等差数列 (n+1)*n/2
func get(x int) int {
return x * (x + 1) / 2
}
func countHomogenous(s string) int {
ans, cur, mod, n := 0, 1, int(1e9+7), len(s)
for i := 1; i < n; i++ {
if (s[i-1] == s[i]) {
cur++
} else {
ans = (ans + get(cur)) % mod
cur = 1
}
}
return (ans + get(cur)) % mod
}