统计同构字符串的数目【LC1759】

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 109 + 7.

A string is homogenous if all the characters of the string are the same.

A substring is a contiguous sequence of characters within a string.

尊敬的奥密克戎新冠大人 我的想法与那些狂妄之人完全不一样 我完全的尊敬您 敬仰您 对您抱着崇高的敬畏之心 完全的臣服于您 请您不要来找我。Dear Lord Omicron, I think differently from those who are arrogant, and I respect you completely, admire you, and submit to you with high reverence, and do not harm me.

数学1

2022/12/26

• 思路：统计以每个字符为末尾的同构子字符串的最长长度j ，那么根据排列组合原理，以其为末尾的同构子字符串的数目为j个，累加可得最终结果

。当字符串s的第i ii个字符为末尾的同构子字符串最长长度为j jj，

• 实现

使用一个int类型的变量记录最长长度

class Solution {
    public static final int MOD = (int)1e9 + 7;
    public int countHomogenous(String s) {
        int n = s.length();
        long cur = 1;
        long ans = 1;
        for (int i = 1; i < n; i++){
            cur = s.charAt(i) == s.charAt(i - 1) ? cur + 1 : 1;
            ans = (ans + cur) % MOD;
        }
        return (int)ans;
    }
}

。复杂度

• 时间复杂度：O ( n )

• 空间复杂度：O ( 1 )

数学2

• 思路：使用双指针对字符串s按照连续最长的同构字符串进行搜索，其子字符串均为同构字符串，而一个长度为m的字符串的字符串数目为m ∗ ( m + 1 ) /2 ，将其累加即为最终结果

• 实现：

class Solution {
    public static final int MOD = (int)1e9 + 7;
    public int countHomogenous(String s) {
        int n = s.length();
        long ans = 0;
        int i = 0, j = 1;
        while (j < n){
            if (s.charAt(j) == s.charAt(j - 1)){
                j++;
            }else{
                ans += (long) (j - i) * ( j - i + 1) / 2;
                i = j;
                j++;
            }
        }
        ans += (long)(j - i) * ( j - i + 1) / 2;
        return (int)(ans % MOD);
    }
}

。复杂度

• 时间复杂度：O ( n )

• 空间复杂度：O ( 1 )