LeetCode 1358 包含所有三种字符的子串数目
🟡 中等 https://leetcode.cn/problems/number-of-substrings-containing-all-three-characters/description/
传统滑窗
这是收集 左边开始到i的数组个数。
class Solution {
public:
int numberOfSubstrings(string s) {
unordered_map<char,int> hash_map;
int left = 0;
int res = 0;
for(int i = 0;i<s.size();i++){
hash_map[s[i]]++;
while(hash_map.size()>=3){
hash_map[s[left]]--;
if(hash_map[s[left]]==0) hash_map.erase(s[left]);
left++;
}
res+=(left-1)-0+1;
}
return res;
}
};
也可以收集 left 到结束的子数组个数。
class Solution {
public:
int numberOfSubstrings(string s) {
unordered_map<char,int> hash_map;
int left = 0;
int res = 0;
for(int i = 0;i<s.size();i++){
hash_map[s[i]]++;
while(hash_map.size()>=3){
res+=s.size()-1-i+1;
hash_map[s[left]]--;
if(hash_map[s[left]]==0) hash_map.erase(s[left]);
left++;
}
}
return res;
}
};
动规
思考以 i 结尾的答案，其开始位置取决于 a b c 其中最晚出现位置的最小值。
使用 last数组维护上次 a b c 出现的最后位置。
首先last初始不能为0，那么设置成什么呢？-2可以吗？可以，但是要额外设置判断条件。可以设置成-1，假设最小的下标为 i，那么答案因该加 i+1， 所以我们要让初始abc都没更新时，答案的更新为0，因此令 i+1 = 0，i= -1，所以初始设置last 为-1.
class Solution {
public:
int numberOfSubstrings(string s) {
int last[3];
fill(last,last+3,-1);
int res = 0;
for(int i = 0;i<s.size();i++){
last[s[i]-'a'] = i;
int left = min(last[0],min(last[1],last[2]));
res+=left-(-1);
}
return res;
}
};