1759. Count Number of Homogenous Substrings

這題也是在周賽中有想到,

如果是”aaa”, 那他的總和會是 6 , 分別是 3 + 2 + 1, “a” “a” “a” “aa” “aa” “aaa”

掌握這個大原則, 當換字母時就算一次

這題比較煩的是在如果超界, 得 % 10⁹ + 7

class Solution {
public:
    long count(long n){
        long res = 0;
        res = ((1 + n) * n) / 2;
        return res;
    }
    int countHomogenous(string s) {
        if(s.size()==0) return 0;
        long res = 0;
        string cur = "";
        cur += s[0];
        for(int i = 1; i < s.size();i++){
            if(s[i] != s[i -1]){
                int size = cur.size();
                res += count(cur.size());
                cur.clear();
                cur += s[i];
            }else{
                cur+= s[i];
            }
        }
        res += count(cur.size());
        return res % (1000000000 + 7);
    }
};

有看到一個更聰明的做法, 就是相同的話我就維持一個count並一直往上加

當字母不一樣時, 就把count歸1, 並且每次都module10⁹ + 7, 非常精簡

class Solution {
public:
 
    int countHomogenous(string s) {
        if(s.size()==0) return 0;
        char cur = s[0];
        int res = 1;
        int count = 1;
        int mod = 1e9 + 7;
        for(int i = 1; i <s.size();i++){
            if(cur == s[i]){
                count = count + 1;
            }else{
                count = 1;
                cur = s[i];
            }
            res = (res + count) % mod;
        }
        return res;
    }
};