题目描述
给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
示例 1：
输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
示例 2：
输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。
示例 3：
输入：s = "abc"
输出：1
提示：
3 <= s.length <= 5 x 10^4s 只包含字符 a，b 和 c 。
解法
方法一：一次遍历
我们用一个长度为 \(3\) 的数组 \(d\) 记录三种字符最近一次出现的位置，初始时均为 \(-1\)。
遍历字符串 \(s\)，对于当前位置 \(i\)，我们先更新 \(d[s[i]]=i\)，然后合法的字符串个数为 \(\min(d[0], d[1], d[2]) + 1\)，累加到答案中。
时间复杂度 \(O(n)\)，其中 \(n\) 为字符串 \(s\) 的长度。空间复杂度 \(O(1)\)。
| class Solution:
def numberOfSubstrings(self, s: str) -> int:
d = {"a": -1, "b": -1, "c": -1}
ans = 0
for i, c in enumerate(s):
d[c] = i
ans += min(d["a"], d["b"], d["c"]) + 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution {
public int numberOfSubstrings(String s) {
int[] d = new int[] {-1, -1, -1};
int ans = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
d[c - 'a'] = i;
ans += Math.min(d[0], Math.min(d[1], d[2])) + 1;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution {
public:
int numberOfSubstrings(string s) {
int d[3] = {-1, -1, -1};
int ans = 0;
for (int i = 0; i < s.size(); ++i) {
d[s[i] - 'a'] = i;
ans += min(d[0], min(d[1], d[2])) + 1;
}
return ans;
}
};
|
| func numberOfSubstrings(s string) (ans int) {
d := [3]int{-1, -1, -1}
for i, c := range s {
d[c-'a'] = i
ans += min(d[0], min(d[1], d[2])) + 1
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | function numberOfSubstrings(s: string): number {
const d: number[] = [-1, -1, -1];
let ans = 0;
for (let i = 0; i < s.length; i++) {
const c = s.charCodeAt(i) - 97;
d[c] = i;
ans += Math.min(d[0], Math.min(d[1], d[2])) + 1;
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | impl Solution {
pub fn number_of_substrings(s: String) -> i32 {
let bytes = s.as_bytes();
let mut d = [-1i32; 3];
let mut ans: i32 = 0;
for i in 0..bytes.len() {
let c = (bytes[i] - b'a') as usize;
d[c] = i as i32;
let mn = d[0].min(d[1]).min(d[2]);
ans += mn + 1;
}
ans
}
}
|
方法二：滑动窗口
我们可以使用滑动窗口的方法求解。维护一个窗口 \([l, r]\) 和一个数组 \(\textit{cnt}\) 记录窗口内各字符的出现次数。
遍历字符串，不断右移右边界 \(r\)，将 \(s[r]\) 加入窗口。若窗口内 \(a\)、\(b\)、\(c\) 均至少出现一次，则不断右移左边界 \(l\)，直到窗口内不再同时包含三种字符为止。
此时，所有以 \(r\) 为右端点且包含 \(a\)、\(b\)、\(c\) 的子字符串的左端点可取 \(0, 1, \ldots, l - 1\)，共 \(l\) 个，累加到答案中。
时间复杂度 \(O(n)\)，其中 \(n\) 为字符串 \(s\) 的长度。空间复杂度 \(O(1)\)。
| class Solution:
def numberOfSubstrings(self, s: str) -> int:
ans = l = 0
cnt = Counter()
for r, c in enumerate(s):
cnt[c] += 1
while cnt['a'] and cnt['b'] and cnt['c']:
cnt[s[l]] -= 1
l += 1
ans += l
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public int numberOfSubstrings(String s) {
int ans = 0, l = 0;
int[] cnt = new int[3];
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
cnt[c - 'a']++;
while (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) {
cnt[s.charAt(l) - 'a']--;
l++;
}
ans += l;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
int numberOfSubstrings(string s) {
int ans = 0, l = 0;
int cnt[3] = {0, 0, 0};
for (int r = 0; r < (int) s.size(); r++) {
cnt[s[r] - 'a']++;
while (cnt[0] && cnt[1] && cnt[2]) {
cnt[s[l] - 'a']--;
l++;
}
ans += l;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | func numberOfSubstrings(s string) int {
ans, l := 0, 0
cnt := [3]int{}
for r := 0; r < len(s); r++ {
cnt[s[r]-'a']++
for cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0 {
cnt[s[l]-'a']--
l++
}
ans += l
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function numberOfSubstrings(s: string): number {
let ans = 0,
l = 0;
const cnt = [0, 0, 0];
for (let r = 0; r < s.length; r++) {
cnt[s.charCodeAt(r) - 97]++;
while (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) {
cnt[s.charCodeAt(l) - 97]--;
l++;
}
ans += l;
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | impl Solution {
pub fn number_of_substrings(s: String) -> i32 {
let bytes = s.as_bytes();
let mut ans = 0;
let mut l = 0;
let mut cnt = [0; 3];
for r in 0..bytes.len() {
cnt[(bytes[r] - b'a') as usize] += 1;
while cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0 {
cnt[(bytes[l] - b'a') as usize] -= 1;
l += 1;
}
ans += l as i32;
}
ans
}
}
|