class Solution {
public:
int countHomogenous(string s) {
}
};
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 <= 105s 由小写字符串组成原站题解
cpp 解法, 执行用时: 20 ms, 内存消耗: 11.4 MB, 提交时间: 2022-12-26 13:06:06
class Solution {
public:
const int mod = 1e9 + 7;
int countHomogenous(string s) {
int n = s.size();
long ans = 0;
for (int i = 0, j = 0; i < n; i = j) {
j = i;
while (j < n && s[j] == s[i]) ++j;
int cnt = j - i;
ans += 1ll * (1 + cnt) * cnt / 2;
ans %= mod;
}
return ans;
}
};
java 解法, 执行用时: 9 ms, 内存消耗: 41.7 MB, 提交时间: 2022-12-26 13:05:46
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countHomogenous(String s) {
int n = s.length();
long ans = 0;
for (int i = 0, j = 0; i < n; i = j) {
j = i;
while (j < n && s.charAt(j) == s.charAt(i)) {
++j;
}
int cnt = j - i;
ans += (long) (1 + cnt) * cnt / 2;
ans %= MOD;
}
return (int) ans;
}
}
golang 解法, 执行用时: 12 ms, 内存消耗: 6 MB, 提交时间: 2022-12-26 13:05:33
func countHomogenous(s string) (ans int) {
n := len(s)
const mod int = 1e9 + 7
for i, j := 0, 0; i < n; i = j {
j = i
for j < n && s[j] == s[i] {
j++
}
cnt := j - i
ans += (1 + cnt) * cnt / 2
ans %= mod
}
return
}
python3 解法, 执行用时: 136 ms, 内存消耗: 15.4 MB, 提交时间: 2022-12-26 13:05:20
class Solution:
def countHomogenous(self, s: str) -> int:
mod = 10**9 + 7
i, n = 0, len(s)
ans = 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
cnt = j - i
ans += (1 + cnt) * cnt // 2
ans %= mod
i = j
return ans
golang 解法, 执行用时: 8 ms, 内存消耗: 6 MB, 提交时间: 2022-12-26 13:05:00
func countHomogenous(s string) (res int) {
const mod int = 1e9 + 7
prev := rune(s[0])
cnt := 0
for _, c := range s {
if c == prev {
cnt++
} else {
res += (cnt + 1) * cnt / 2
cnt = 1
prev = c
}
}
res += (cnt + 1) * cnt / 2
return res % mod
}
javascript 解法, 执行用时: 76 ms, 内存消耗: 45.1 MB, 提交时间: 2022-12-26 13:04:47
/**
* @param {string} s
* @return {number}
*/
var countHomogenous = function(s) {
const MOD = 1000000007;
let res = 0;
let prev = s[0];
let cnt = 0;
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c === prev) {
cnt++;
} else {
res += (cnt + 1) * cnt / 2;
cnt = 1;
prev = c;
}
}
res += (cnt + 1) * cnt / 2;
return res % MOD;
};
cpp 解法, 执行用时: 16 ms, 内存消耗: 11.3 MB, 提交时间: 2022-12-26 13:04:31
class Solution {
public:
int countHomogenous(string s) {
long long res = 0;
long long mod = 1e9 + 7;
int prev = s[0];
int cnt = 0;
for (auto c : s) {
if (c == prev) {
cnt++;
} else {
res += (long long)(cnt + 1) * cnt / 2;
cnt = 1;
prev = c;
}
}
res += (long long)(cnt + 1) * cnt / 2;
return res % mod;
}
};
java 解法, 执行用时: 8 ms, 内存消耗: 41.6 MB, 提交时间: 2022-12-26 13:03:58
class Solution {
public int countHomogenous(String s) {
final int MOD = 1000000007;
long res = 0;
char prev = s.charAt(0);
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == prev) {
cnt++;
} else {
res += (long) (cnt + 1) * cnt / 2;
cnt = 1;
prev = c;
}
}
res += (long) (cnt + 1) * cnt / 2;
return (int) (res % MOD);
}
}
python3 解法, 执行用时: 96 ms, 内存消耗: 16.4 MB, 提交时间: 2022-12-26 13:03:44
class Solution:
def countHomogenous(self, s: str) -> int:
res = 0
for k, g in groupby(s):
n = len(list(g))
res += (n + 1) * n // 2
return res % (10 ** 9 + 7)