统计同构子字符串的数目

5677. 统计同构子字符串的数目

难度中等

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

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

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

示例 1：

输入：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

示例 2：

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

示例 3：

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

提示：

• 1 <= s.length <= 105
• s 由小写字符串组成

dp[i]代表以i结尾的当前字符构成的同构字符串的数量,总数量是以每个字符结尾的同构字符串的数量和

例1：

s = a b b c c c a a
dp={1,1,2,1,2,3,1,2}
res=1+1+2+1+2+3+1+2=13
以字符'c'为例，遍历到第一个c的时候，c只能组成一个；
遍历到第二个c的时候，第二个c能组成一个，与前一个共同构成一个（包含两个字符）；
遍历到第三个c的时候，第三个c能组成一个，与前一个共同构成一个（包含两个字符），与前两个共同构成一个（包含三个字符）

$(a + b) % p = (a % p + b % p) % p$
这是一个重要公式，求模时每一步求模，最后对结果求模所得的结果和最后一次求模的计算结果相同

class Solution {
    public int countHomogenous(String s) {
        int mod=1000000007;
        char[] arr = s.toCharArray();
        int n = s.length();

        int[] dp = new int[n];
        dp[0] = 1;
        long res = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = arr[i] == arr[i - 1] ? dp[i - 1] + 1 : 1;
            res=(res+dp[i])%mod;
        }
        return (int)(res%mod);
    }
}

时间复杂度$O(n)$

赏

谢谢你请我吃糖果

微信