Medium

题目描述

给你一个字符串 s ，返回 s 中 同构子字符串 的数目。由于答案可能很大，只需返回对 10^9 + 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 <= 10^5
  • s 由小写字母组成

解题思路

解题思路

这道题要求计算同构子字符串的数目。关键观察是：对于长度为 k 的连续相同字符序列，它包含的同构子字符串数目为 k(k+1)/2*。

具体分析：

  • 长度为 k 的相同字符序列可以形成：
    • k 个长度为 1 的子串
    • (k-1) 个长度为 2 的子串
    • …
    • 1 个长度为 k 的子串
  • 总数为：k + (k-1) + … + 1 = k*(k+1)/2

算法步骤：

  1. 遍历字符串，找到每段连续相同字符的长度
  2. 对每段长度为 len 的序列，贡献 len*(len+1)/2 个同构子字符串
  3. 累加所有贡献，记得取模防止溢出

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

另一种思路是动态规划：用 dp 表示以当前位置结尾的同构子字符串数目，但本质上和上述方法等价。

代码实现

class Solution {
public:
    int countHomogenous(string s) {
        const int MOD = 1e9 + 7;
        long long result = 0;
        int n = s.length();
        
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                j++;
            }
            long long len = j - i;
            result = (result + len * (len + 1) / 2) % MOD;
            i = j;
        }
        
        return result;
    }
};

class Solution:
    def countHomogenous(self, s: str) -> int:
        MOD = 10**9 + 7
        result = 0
        n = len(s)
        i = 0
        
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            length = j - i
            result = (result + length * (length + 1) // 2) % MOD
            i = j
        
        return result

public class Solution {
    public int CountHomogenous(string s) {
        const int MOD = 1000000007;
        long result = 0;
        int n = s.Length;
        
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                j++;
            }
            long len = j - i;
            result = (result + len * (len + 1) / 2) % MOD;
            i = j;
        }
        
        return (int)result;
    }
}

var countHomogenous = function(s) {
    const MOD = 1e9 + 7;
    let result = 0;
    const n = s.length;
    
    for (let i = 0; i < n; ) {
        let j = i;
        while (j < n && s[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个字符串一次
空间复杂度O(1)只使用常数额外空间

相关题目