b_lc_统计同构子字符串的数目(找规律 / dp)

字符串 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
}
上一篇:【NOI Online#2 提高组】子序列问题


下一篇:lc最大子序和