mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
116 lines
5.1 KiB
Markdown
116 lines
5.1 KiB
Markdown
# [395. Longest Substring with At Least K Repeating Characters](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/)
|
||
|
||
# 思路
|
||
给定一个只包含小写字母的字符串s和整数k，求s的子串中满足子串中的字母出现次数都不少于k的子串的最大长度。
|
||
|
||
## 思路一、暴力
|
||
此题可以用暴力解法，但是直接暴力可能会超时，需要稍微改进一点。我们如何判断每个字母出现次数是否不小于k呢，
|
||
如果我们用一个长为26的数组cnt记录每个字母的出现次数，然后需要每次遍历一遍这个数组来判断是否满足提交，效率不高。
|
||
由于只可能是26个小写字母，所以我们新增一个32位整数mask来记录某个字母是否是满足条件的，
|
||
若某一位为0则对应字母是满足条件的（即要么没这个字母要么这个字母出现次数不小于k），所以我们只需判断整个mask是否为0就可以判断是否全部满足条件了。
|
||
|
||
具体来讲，我们用两层循环，第一层循环为子串的左边界start，第二层循环则是子串的右边界end。
|
||
每次进入第二层循环时都需要初始化数组cnt和mask，在第二层循环内部我们需要更新mask并判断mask是否为0，若是即可尝试更新结果。
|
||
|
||
时间复杂度O(n^2)，空间复杂度O(1)。
|
||
|
||
> **如果只有小（大）写字母，即只有26个字符，那么用一个32为整数来进行记录一些bool状态是很常见的思路。**
|
||
|
||
## 思路二、分治
|
||
|
||
此题可以考虑用分治法。那么要如何进行划分呢，由于要满足出现次数不小于k，我们可以考虑先统计每个字母的出现次数，
|
||
出现次数小于k的那些字母肯定不可能出现在合法子串中的，即可以将这些字母作为分界线对字符串s进行划分。递归出口就是每次字母出现次数都不小于k。
|
||
|
||
这应该是此题最好写的方法，亲测也是最快的（0ms）。
|
||
|
||
## 思路二、双指针
|
||
|
||
因为题目中限定了字符串中只有26个小写字母，所以最后满足题意的子串中的unique字母数一定是在范围[1, 26]内，
|
||
我们可以从1到26枚举unique字母数（记为cnt），对于每个cnt，维护一个窗口左右指针start和end，我们不断更新end和start，保持窗口内的子串的unique字符数（记为uniqueCnt）不超过cnt，
|
||
为此需要用一个大小为26的数组charCnt来记录窗口内每个字母的出现次数。
|
||
|
||
怎样更新start和end呢？我们让end不断加1更新，而start的更新需要视情况而定：
|
||
> 先判断end字符是否是一个全新的字符，若是那么需要让uniqueCnt加1，此时可能uniqueCnt超过cnt了，所以我们需要将start右移直到uniqueCnt不超过cnt。
|
||
每次更新好end和start后还需要判断窗口内每个字符串是否满足条件，若是应该尝试更新res。
|
||
|
||
外层循环固定26次，内存循环中end和start都是只可能往右不可能往左的，所以是线性复杂度的，所以总的时间复杂度也是线性的。
|
||
|
||
# C++
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int longestSubstring(string s, int k) {
|
||
int start = 0, res = 0;
|
||
for(int start = 0; start < s.size(); start++){
|
||
int mask = 0;
|
||
vector<int>cnt(26, 0);
|
||
for(int end = start; end < s.size(); end++){
|
||
int c = s[end] - 'a';
|
||
if(++cnt[c] >= k) mask &= (~(1 << c)); // 将对应位置0
|
||
else mask |= (1 << c); // 将对应位置1
|
||
|
||
if(!mask) res = max(res, end - start + 1);
|
||
}
|
||
}
|
||
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int longestSubstring(string s, int k) {
|
||
int res = 0, n = s.size();
|
||
|
||
vector<int>cnt(26, 0); // 统计每个字母的出现次数
|
||
for(auto &c: s) cnt[c - 'a']++;
|
||
|
||
int start = 0;
|
||
bool tag = true;
|
||
for(int i = 0; i < n; i++){
|
||
if(cnt[s[i] - 'a'] < k){
|
||
tag = false;
|
||
if(i > start)
|
||
res = max(res, longestSubstring(s.substr(start, i - start), k));
|
||
start = i + 1;
|
||
}
|
||
}
|
||
// tag为true说明每个字母出现次数均不小于k
|
||
return tag ? s.size() : max(res, longestSubstring(s.substr(start, n - start), k));
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路三
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int longestSubstring(string s, int k) {
|
||
int res = 0, n = s.size();
|
||
for (int cnt = 1; cnt <= 26; ++cnt) {
|
||
int start = 0, end = 0, uniqueCnt = 0;
|
||
vector<int> charCnt(26);
|
||
for(; end < n; end++){
|
||
if (charCnt[s[end] - 'a']++ == 0) uniqueCnt++;
|
||
|
||
while (uniqueCnt > cnt)
|
||
if (--charCnt[s[start++] - 'a'] == 0) uniqueCnt--;
|
||
|
||
bool valid = true;
|
||
for (int j = 0; j < 26; ++j)
|
||
if (charCnt[j] > 0 && charCnt[j] < k)
|
||
{valid = false; break;}
|
||
|
||
if(valid) res = max(res, end - start + 1);
|
||
}
|
||
}
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
|