1180. 统计只含单一字母的子串

输入： "aaaba"
输出： 8
解释： 
只含单一字母的子串分别是 "aaa"， "aa"， "a"， "b"。
"aaa" 出现 1 次。
"aa" 出现 2 次。
"a" 出现 4 次。
"b" 出现 1 次。
所以答案是 1 + 2 + 4 + 1 = 8。

解法：分组（双指针）

思路

将单个字母的最大字串分成多个组，每个组算 1 到 组长的累加和，再将所有组的累加和加在一起就是答案。

1 到 n 的累加和，利用公式 $1+...+n=n(n+1)/2$ 可以降到 $O(1)$。

分组则可以用双指针。

复杂度

时间复杂度：$O(N)$

空间复杂度：$O(1)$

代码

class Solution {
public:
    int countLetters(string s) {
        int res = 0;
        s += '*'; // 利用 * 占位，可以正确结算最后一组。cpp 中 string 末尾加一个字符时间与空间复杂度是 O(1)
        int i = 0, j = 0;
        while (i < s.size()) {
            if (s[i] == s[j]) i++;
            else {
                int n = i - j;
                res += n * (n + 1) >> 1;
                j = i;
            }
        }
        return res;
    }
};