一、解题背景：
字符串的子串应该是常见的一类有关字符串的算法题目，这里我将leetcode的相关几道题汇总了一下，写了一些具体的思路和多种的求解方法。
二、问题求解：
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
/***********************************************************************/
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
class Solution {
public:
// 方法1：
int lengthOfLongestSubstring1(string s) {
unordered_map<char,int> mp; // 记录的是索引位置
int ans = 0, i = 0;
for (int j=0; j<s.size(); j++) {
if (mp.find(s[j])!=mp.end()) {
i = max(mp[s[j]], i);
}
ans = max(ans, j-i+1);
mp[s[j]] = j+1; // 保存对应字符后边的位置索引，可能作为下一次无重复字符串起点
}
return ans;
}
// 方法2：
int lengthOfLongestSubstring1(string s) {
unordered_map<char,int> mp; // 记录的是字符出现的次数
int ans = 0;
for (int i=0, j=0; j<s.size(); j++) {
mp[s[j]]++;
while (mp[s[j]]>1) { // 同样这个步骤也是为了找到相同字符的后一个位置
mp[s[i++]]--;
}
ans = max(ans, j-i+1);
}
return ans;
}
};
159. 至多包含两个不同字符的最长子串
给定字符串 s，判断最长的只含有一个或者两个字符的子串的长度。
input_str = “kkkk”
answer = 4
解释：最长子串是 kkkk。
/***********************************************************************/
input_str = “abdyd”
answer = 3
解释：满足条件的最长子串是 dyd。
class Solution {
public:
bool cmp(const pair<char, int> left,const pair<char, int> right) {
return left.second<right.second;
}
int lengthOfLongest2DisSubstring(string s) {
int ans = 1;
unordered_map<char, int> mp;
for (int j=0, i=0; j<s.size();j++) {
mp[s[j]] = j;
if(mp.size()==3) {
auto iter = min_element(mp.begin(), mp.end(), cmp); // 找到最小的value的键值对
i = iter->second+1;
mp.erase(iter);
}
ans = max(ans, j-i+1);
}
return ans;
}
};
395. 至少有 K 个重复字符的最长子串
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
实例1：
输入：s = “aaabb”, k = 3
输出：3
解释：最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。
实例2：
输入：s = “ababbc”, k = 2
输出：5
解释：最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。
class Solution {
public:
// 这里主要采用了分治的策略，从而使得问题拆分小，这里的核心是将整个字符串中次数未超过k次的作为分隔符来进行计算出现次数至少k次的最长子串。
int dfs(string &s, int l, int r, int k, int res=0) {
if (l>r) return 0;
unordered_map<char,int> mp;
for (int i=l; i<=r; i++)
mp[s[i]]++;
vector<int> pos;
pos.push_back(l-1);
for (int i=l; i<=r; i++)
if (mp[s[i]]<k) pos.push_back(i);
pos.push_back(r+1);
if (pos.size()==2) return r-l+1;
for (int i=0; i<pos.size()-1; i++) {
res = max(res, dfs(s, pos[i]+1, pos[i+1]-1, k, res));
}
return res;
}
int longestSubstring(string s, int k) {
if (s.size()==0 || s.size()<k) return 0;
if (k<=1) return s.size();
return dfs(s,0,s.size()-1,k,0);
}
};
参考的思路：来源leetcode题解
//分治：对于一个字符串来说，如果要求子串最少出现k次，那么如果某些字母出现的次数小于k,
//这些字母一定不会出现在最长的子串中，并且这些字母将整个字符子串分割成小段，这些小段有可能是最长的
//但是由于被分割了，还是要检查这一小段，如果某些字母出现的次数小于k,会将小段继续分割下去,
//比如字符串"aacbbbdc"，要求最少出现2次,我们记录左右闭区间，，
//第一轮[0,7]，处理"aacbbbdc"，d只出现了一次不满足，于是递归解决区间[0,5]、[7,7]
//第二轮[0,5]，处理"aacbbb"， c只出现了一次不满足，于是递归解决区间[0,1]、[3,4]
//第二轮[7,7]，处理"c"， c只出现了一次不满足，不继续递归
//第三轮[0,1]，处理"aa"， 满足出现次数>=2,res=2
//第三轮[3,4]，处理"bbb"， 满足出现次数>=2 res=3;