1.题目描述
1759. 统计同构子字符串的数目
难度中等43
给你一个字符串 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
2.解题思路与代码
2.1 解题思路
典型的滑动窗口题目,我们使用 left 和 right 两个指针来表示滑动窗口的左右边界,首先记录初始位置的字符 ch,然后开始移动右边界 right,并记录 right 位置上的字符。此时比较 right 上的字符与前面记录的字符是否相同,如果相同统计当前窗口字符数并累加到结果上即 ans+=right-left+1。如果不相同说明前面一个相同字符子串已经结束,缩小窗口,让 left 移动到 right 上重新开始计算,并将 ch 记录当前 right 位置上的字符,由于单个字符也算相同字符子串,因此也要累加计算 ans+=right-left+1。
以字符串 “abbcccaa” 为例,初始化才开始的时候让 left 和 right 指向 0 位置,并且此时 ch 记录 ‘a’。
![](https://img-blog.csdnimg.cn/img_convert/e194e65b18c9365cc39c6925bd7080b2.png)
开始移动 right ,当 right 移动到 b 时,此时 right 字符与 ch 记录不同,需要将 left 移动到 right 位置并重新记录 ch 为当前 right 字符 ‘b’
![](https://img-blog.csdnimg.cn/img_convert/9d21b451b3f59042350f9a4e5e19a8f7.png)
继续移动 right 直到 right 指向字符 c,此时将 left 移动到 right 并在此记录 ch 为字符 ‘c’。重复这一系列操作直到字符串遍历完成。最后返回 ans 即可。
![](https://img-blog.csdnimg.cn/img_convert/6ac87fece7cbc7cdcc2b60b44d5a9ef3.png)
2.2 代码
class Solution {
public int countHomogenous(String s) {
long ans = 0;
int l = 0, r = 0;
char ch = s.charAt(r);
while (r < s.length()) {
if (ch!=s.charAt(r)){
l = r;
ch = s.charAt(r);
}
ans += r - l + 1;
r++;
}
return (int) (ans % (Math.pow(10, 9) + 7));
}
}
2.3 测试结果
通过测试
![测试结果](https://img-blog.csdnimg.cn/img_convert/258c5dd4c4935a6ea5f1830846fcdecd.png)
3.总结
- 使用字符 ch 记录字符,并用滑动窗口统计子串个数
- 如果遇到不同字符移动 left 到 right 位置并重新记录 ch 为当前字符
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)