1759-统计同质子字符串的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

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

方法一：数学

思路与算法

题目给出一个长度为 n 的字符串 s，并给出「同构字符串」的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。现在我们需要求 s 中「同构子字符串」的数目。
因为「同构子字符串」为一个连续的字符序列且需要序列中的字符都相同，那么我们首先按照连续相同的字符来对字符串 s 进行分组，比如对于字符串 abbcccaa" 我们的分组结果为 [a”,bb",ccc”,``aa”]。因为对于一个组中字符串的任意子字符串都为「同构子字符串」，而一个长度为 m 的字符串的子字符串的数目为 \dfrac{m \times (m + 1)}{2。那么我们对于每一个组来统计其贡献的「同构子字符串」数目并求和即可。

代码

[sol1-Python3]
1
2
3
4
5
6
7
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)
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int CountHomogenous(string s) {
        const int MOD = 1000000007;
        long res = 0;
        char prev = s[0];
        int cnt = 0;
        foreach (char c in s) {
            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);
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int countHomogenous(char * s) {
    long long res = 0;
    long long mod = 1e9 + 7;
    int prev = s[0];
    int cnt = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == prev) {
            cnt++;
        } else {
            res += (long long)(cnt + 1) * cnt / 2;
            cnt = 1;
            prev = s[i];
        }
    }
    res += (long long)(cnt + 1) * cnt / 2;
    return res % mod;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 字符串 s 的长度。
  • 空间复杂度：O(1)。仅使用常量空间。
 Comments
On this page
1759-统计同质子字符串的数目