LeetCode题目笔记——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 <= 10⁵
s 由小写字符串组成

题目链接

题目难度——中等

方法一：数学

  根据题目意思，让我们来数一数 “abbcccaa”这个字符串中的子字符串，我们可以将其分为“a”，“bb”，“ccc”，“aa”这几个部分，对“a”，它只有一个字符，同构字符串数也是1，对“bb”，他可以是两个单独的“b”，也可以是连在一起的“bb”，所以一共是3，对“ccc”，它可以是一个“c”，也可以是两个“c”，还可以是三个“c”，所以一共是6，因此，就是像数连续出现的字符可以有多少种情况一样，记一个字符出现的次数为count，那它的同构字符串数量就是(count + 1) * count / 2。

代码/C++

class Solution {
public:int countHomogenous(string s) {long long res = 0, count = 0, mod = 1e9 + 7;char pre = s[0];string ss = s + "E";for(int i = 0; i < ss.size(); i++){if(ss[i] == pre){count++;continue;}res += (1 + count) * count / 2;count = 1;pre = ss[i];}return res % mod;}
};

代码/Python

class Solution:def countHomogenous(self, s: str) -> int:res = 0for k, g in groupby(s):n = len(list(g))res += (n + 1) * n // 2return res % (10 ** 9 + 7)

总结

  都要遍历一遍字符串，所以时间是O(N)，用了一个多的字符串，所以空间是O(N)，也可以不用这个多的，在循环退出后外面再算一次计数就可以，那样可以让空间成为O(1)。