跳转至

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

问题描述#

给你一个字符串 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 由小写字符串组成

解题思路#

统计连续字符的数量即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def countHomogenous(self, s: str) -> int:
        s += '$'
        n = len(s)

        MOD = 10 ** 9 + 7
        ans, pre, t = 0, s[0], 1

        for i in range(1, n):
            if s[i] != pre:
                ans = (ans + t * (t + 1) // 2) % MOD
                t = 1
            else:
                t += 1
            pre = s[i]

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countHomogenous(string s) {
        s += '$';
        int n = s.size();
        long long ans = 0, t = 1, MOD = 1e9 + 7;
        char pre = s[0];

        for (int i = 1; i < n; ++i) {
            if (s[i] != pre) {
                ans = (ans + t * (t + 1) / 2) % MOD;
                t = 1;
            } else ++t;
            pre = s[i];
        }

        return ans;
    }
};
返回顶部

在手机上阅读