Leetcode 1759 - Count Number of Homogenous Substrings

題目

Problem#

給你一個字串 s 要你回傳所有 homogeneous 的子字串的個數總和。homogenous 指的是字串裡的所有字元都一樣。
答案可能很大要 mod $10^9+7$

測資限制#

• $1 \le n \le 10^5$

想法#

題目要求所有同字元子字串的個數總和，對於字串 aaa 來說，他有 a, aa, aaa 這三個同字元子字串，分別出現 3, 2, 1 次，答案是 $3+2+1=6$，可以觀察發現答案是從 1 累加到子字串長度，也就是 (1+n)*n/2。當前個字元與當前字元不同時，我們就知道目前子字串的最大長度，所以題目就變成了，找出所有子字串長度，接著帶入公式累加即可。

AC Code#

Copy

class Solution {
public:
    const int mod = 1e9+7;
    inline int calc(long long n)
    {
        return ((n+1)*n/2) % mod;
    }
    int countHomogenous(string s)
    {
        int n = s.size();
        int cnt = 1;
        int ans = 0;
        for(int i = 1; i < n; i++)
        {
            if(s[i] != s[i-1])
            {
                ans += calc(cnt);
                cnt = 1;
            }
            else
                cnt++;
        }
        ans += calc(cnt);
        return ans;
    }
};

view raw leetcode/1759.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(1)$