.jpg)
给你一个字符串 s ，返回 s 中 同构子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。
同构字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。
子字符串 是字符串中的一个连续字符序列。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-number-of-homogenous-substrings
题解
分析
- 同构字符串必须是连续且相同的字符串，单个字符为1个同构字符串
- 子字符串中的同构字符串个数满足数学关系式：sIndex * (sIndex+1) / 2
- sIndex为子字符串的长度，字符串中的字符全部相等
上代码（java）
class Solution {
public int countHomogenous(String s) {
// 获取第一个字符
char ch = s.charAt(0);
// 计算的字符串长度
long sIndex = 0;
// 结果
long result = 0;
for(int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ch) {
sIndex++;
}
else {
// 子字符串的同构字符串
result += (sIndex + 1) * sIndex / 2;
sIndex = 1;
ch = s.charAt(i);
}
}
// 计算最后一组子字符串的同构字符串
result += (sIndex + 1) * sIndex / 2;
return Math.toIntExact(result % (10^9 + 7));
}
}
测试用例通过（8/84）
执行参数为："vvvvvvllll"时，期望输出：31，程序输出：5
定位到的原因是：程序最后的return语句取余的是10^9 + 7，而不是1000000007
修改后的程序
class Solution {
public int countHomogenous(String s) {
// 获取第一个字符
char ch = s.charAt(0);
// 计算的字符串长度
long sIndex = 0;
// 结果
long result = 0;
for(int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ch) {
sIndex++;
}
else {
// 子字符串的同构字符串
result += (sIndex + 1) * sIndex / 2;
sIndex = 1;
ch = s.charAt(i);
}
}
// 计算最后一组子字符串的同构字符串
result += (sIndex + 1) * sIndex / 2;
return Math.toIntExact(result % 1000000007);
}
}
结果
- 通过测试用例：84/84
- 时间复杂度O(n)
- 空间复杂度O(1)
评论区