题目描述

给你一个字符串 s ，返回 s 中 同构子字符串 的数目。由于答案可能很大，只需返回对 10^9 + 7 取余 后的结果。

同构字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。

子字符串 是字符串中的一个连续字符序列。

样例

输入：s = "abbcccaa"
输出：13
解释：同构子字符串如下所列：
"a"   出现 3 次。
"aa"  出现 1 次。
"b"   出现 2 次。
"bb"  出现 1 次。
"c"   出现 3 次。
"cc"  出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

输入：s = "xy"
输出：2
解释：同构子字符串是 "x" 和 "y" 。

输入：s = "zzzzz"
输出：15

提示：

• 1 <= s.length <= 10^5
• s 由小写字符串组成

算法分析

双指针

• 1、可以发现，对于某个子字符串aaaaa...，n个a的连串，一共有(1 + n) * n / 2个同构子字符串
• 2、通过双指针算法，截取出每一段相同符号的连续字符，累加到res即可

时间复杂度 $O(n)$

C++ 代码

const int mod = 1000000000 + 7;
typedef long long LL;
class Solution {
public:
    LL get(int x)
    {
        return (LL)(1 + x) * x / 2;
    }
    int countHomogenous(string s) {
        int n = s.size();
        LL res = 0;
        for(int i = 0;i < n;i ++)
        {
            int j = i;
            while(j < n && s[j] == s[i]) j ++;
            res = (res + get(j - i)) % mod;
            i = j - 1;
        }
        return res;
    }
};