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
}

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

原文：https://www.cnblogs.com/wdt1/p/14403373.html