最长无重复子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入：字符串
输出：最长无重复子串的长度
思路：双指针/滑动窗口
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
while(cin >> s){
// 双指针法 或者叫滑动窗口法
unordered_map<char, int> hash;
int res = 0;
for (int i = 0, j = 0; i < s.size(); i++) {
hash[s[i]]++;
while (hash[s[i]] > 1) hash[s[j++]]--;
res = max(res, i - j + 1);
}
cout << res << endl;
}
return 0;
}
最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
输入：字符串
输出：最长回文子串
思路：中心扩展法，也可以用动规
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
// 中心扩展法
string palindrome(string s, int l, int r) {
while (l >= 0 && r < s.size() && s[l] == s[r]) {
l--, r++;
}
return s.substr(l + 1, r - l - 1);
}
int main() {
string s;
while (cin >> s) {
string res;
for (int i = 0; i < s.size(); i++) {
string s1 = palindrome(s, i, i);
string s2 = palindrome(s, i, i + 1);
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
cout << res << endl;
}
return 0;
}
字符串转整数
请你来实现一个 atoi 函数，使其能将字符串转换成整数。在任何情况下，若函数不能进行有效的转换时，请返回 0 。
输入：字符串
输出：字符串对应的整数
思路：逐一转换，注意判断越界的代码！！！
判断越界代码模板
1
2
3
4
5
6
7
8
int res = 0;
for(auto n:nums){
// 正数越界情况
if(res > INT_MAX / 10 || (res == INT_MAX / 10 && n > 7)) return INT_MAX;
// 负数越界情况
if(res < INT_MIN / 10 || (res == INT_MIN / 10 && n < -8)) return INT_MIN;
}
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
int soi(string s) {
if (s.empty()) return 0;
int idx = 0, res = 0, sign = 1;
while (idx < s.size() && s[idx] == ' ') idx++;
if (idx < s.size()) {
if (s[idx] == '-') {
sign = -1;
idx++;
} else if (s[idx] == '+')
idx++;
}
while (idx < s.size()) {
auto c = s[idx];
if (c < '0' || c > '9') break;
int t = sign * (c - '0');
// 注意这个判断溢出的代码
if (res > INT_MAX / 10 || (res == INT_MAX / 10 && t > 7))
return INT_MAX;
if (res < INT_MIN / 10 || (res == INT_MIN / 10 && t < -8))
return INT_MIN;
res = res * 10 + t;
idx++;
}
return res;
}
int main() {
string s;
while (cin >> s) {
cout << soi << endl;
}
return 0;
}
正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
- ’.’ 匹配任意单个字符；
- ‘*’ 匹配零个或多个前面的那一个元素。 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
输入：字符串和模式串
输出：是否匹配
思路：动态规划，回溯法
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
// 回溯法
bool dfs(string s, string p, int sIdx, int pIdx) {
if (pIdx == p.size()) return sIdx == s.size();
bool firstMatch =
(sIdx != s.size() && (p[pIdx] == s[sIdx] || p[pIdx] == '.'));
if (pIdx + 1 < p.size() && p[pIdx + 1] == '*') {
return dfs(s, p, sIdx, pIdx + 2) ||
(firstMatch && dfs(s, p, sIdx + 1, pIdx));
} else
return firstMatch && dfs(s, p, sIdx + 1, pIdx + 1);
}
int main() {
string s, p;
while (cin >> s >> p) {
vector<vector<bool>> dp(s.size() + 1,
vector<bool>(p.size() + 1, false));
dp[0][0] = true;
// 考虑 "" 和a*a*a*匹配的情况
for (int i = 2; i <= p.size(); i += 2) {
if (p[i - 1] == '*') dp[0][i] = dp[0][i - 2];
}
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= p.size(); j++) {
// 当前字符匹配
if (p[j - 1] == '.' || s[i - 1] == p[j - 1])
dp[i][j] = dp[i - 1][j - 1];
// 当前模式字符是 '*' 时
if (p[j - 1] == '*') {
// 如果 '*' 的前一个字符和匹配串的当前字符不匹配
if (p[j - 2] != s[i - 1] && p[j - 2] != '.')
dp[i][j] = dp[i][j - 2];
else
// 否则匹配的话，可能匹配多次，匹配 1 次，匹配 0 次
dp[i][j] =
dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2];
}
}
}
cout << dp[s.size()][p.size()] << endl;
}
return 0;
}
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ““。
输入：字符串数组
输出：最长公共前缀
思路：水平线性扫描
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
// 暴力扫描
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) {
return "";
}
string temp = strs[0];
int index = 0;
for (index; index < temp.size(); index++) {
for (int i = 0; i < strs.size(); i++) {
if (temp[index] != strs[i][index]) {
return temp.substr(0, index);
}
}
}
return temp;
}
int main() {
vector<string> strs;
string s;
while (cin >> s) {
strs.push_back(s);
}
// 水平扫描法
string prefix = strs[0];
for (int i = 1; i < strs.size(); i++) {
// 如果当前字符串中不存在前缀prefix，则丢掉前缀的最后一个字符直到存在。
while (strs[i].find(prefix) != 0) {
prefix = prefix.substr(0, prefix.size() - 1);
if (prefix.empty()) {
puts(" ");
}
}
}
cout << prefix << endl;
return 0;
}
最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
输入：两个字符串
输出：最小覆盖子串
思路：滑动窗口法(1)使用双指针技巧，初始化l和r为0，把[l,r]称为一个窗口；(2)先不断增加r使得窗口满足字符串需求；(3)此时停止r的增加，而是增加l以缩小窗口，直至窗口中的字符串不在符合要求，每次增加l，都要更新一轮的结果。(4)重复(2)(3)直至r到达字符串的尽头。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
while (cin >> s >> t) {
// 两个哈希表
unordered_map<char, int> need, window;
for (auto c : t) need[c]++;
int l = 0, r = 0, idx = 0;
int matched = 0, minLen = INT_MAX;
while (r < s.size()) {
auto c = s[r];
// 如果需求字符串包含当前字符，则入窗口
if (need.count(c)) {
window[c]++;
// 统计窗口中和需求字符串的匹配字符数
if (window[c] == need[c]) matched++;
}
r++;
// 如果窗口已经满足需求，则缩小窗口大小
while (matched == need.size()) {
// 更新最小覆盖子串长度
if (r - l < minLen) {
minLen = r - l;
idx = l;
}
auto c = s[l];
// 缩小窗口
if (need.count(c)) {
window[c]--;
if (window[c] < need[c]) matched--;
}
l++;
}
}
string res = minLen == INT_MAX ? "" : s.substr(idx, minLen);
cout << res << endl;
}
return 0;
}
最短编辑距离
给你两个单词 s1 和 s2，请你计算出将 s1 转换成 s2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符; 删除一个字符; 替换一个字符。
输入：两个单词字符串
输出：最短编辑距离
思路：动态规划
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
while (cin >> s1 >> s2) {
vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
for (int i = 0; i <= s1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= s2.size(); j++) dp[0][j] = j;
for (int i = 1; i <= s1.size(); i++) {
for (int j = 1; j <= s2.size(); j++) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
// 依次是插入 删除 替换
dp[i][j] = min(dp[i][j - 1] + 1,
min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1));
}
}
cout << dp[s1.size()][s2.size()] << endl;
}
return 0;
}
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
输入：两个字符串
输出：最长公共子序列
思路：动态规划
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
while (cin >> s1 >> s2) {
vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
for (int i = 1; i <= s1.size(); i++) {
for (int j = 1; j <= s2.size(); j++) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
// 不相等说明当前字符不能同时出现
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
cout << dp[s1.size()][s2.size()] << endl;
}
return 0;
}
最长回文子序列
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
输入：字符串
输出：最长回文子序列的长度
思路：动态规划
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
while (cin >> s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
// base case
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
// 注意这儿需要反着遍历
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i + 1; j < s.size(); j++) {
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
// 如果不相等，说明这两个字符不能同时出现的区间，分别将字符加到原来的区间，取其中较大者
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
cout << dp[0][s.size() - 1] << endl;
}
return 0;
}
验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
输入：字符串
输出：是否是回文串
思路：双指针
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
bool isNum(char c) {
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
(c >= '0' && c <= '9'))
return true;
return false;
}
int main() {
string s;
while (cin >> s) {
int l = 0, r = s.size() - 1;
bool isPalindrome = true;
while (l < r) {
while (isNum(s[l]) && l < r) l++;
while (isNum(s[r]) && l < r) r--;
if (toupper(s[l]) != toupper(s[r])) {
isPalindrome = false;
break;
}
l++, r--;
}
if (isPalindrome)
cout << "yes" << endl;
else
cout << "false" << endl;
}
return 0;
}
分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
输入：字符串
输出：所有可能的分割方案
思路：回溯 + 剪枝 每个节点表示截取剩余的字符串，产生前缀字符串时，判断前缀是否是回文，如果是回文，则分割，否则，剪枝；叶子结点是空字符串时，此时，从根节点到叶结点的路径就是结果集中的一个解。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
vector<vector<string>> res;
// 判断是否是回文
bool check(string s, int l, int r) {
while (l < r) {
if (s[l] != s[r]) return false;
}
return true;
}
void dfs(string s, int begin, vector<string> path) {
if (s.size() == begin) {
res.push_back(path);
return;
}
for (int i = begin; i < s.size(); i++) {
// 注意这儿 可以进一步优化
if (!check(s, begin, i)) continue;
path.push_back(s.substr(begin, i - begin + 1));
dfs(s, i + 1, path);
path.pop_back();
}
}
int main() {
string s;
while (cin >> s) {
res.clear();
vector<string> path;
dfs(s, 0, path);
for (int i = 0; i < res.size(); i++) {
for (auto s : res[i]) {
cout << s << ' ';
}
cout << endl;
}
}
return 0;
}
字符串匹配之KMP算法
字符串匹配。时间复杂度$O(n)$。空间复杂度$O(m)$
输入：字符串 和 模式串
输出：字符串中第一次匹配的位置
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
int search(string s, string p) {
int M = p.size(), N = s.size();
// 动态数组 dp[状态][字符] = 下一个状态
vector<vector<int>> dp(M, vector<int>(256, 0));
// base case
dp[0][p[0]] = 1;
// 影子状态初始化为0
int X = 0;
// 利用模式串构建状态转移图
for (int j = 1; j < M; j++) {
for (int c = 0; c < 256; c++) {
if (p[j] == c)
dp[j][c] = j + 1;
else
dp[j][c] = dp[X][c];
}
X = dp[X][p[j]];
}
int j = 0; // 记录状态 模式初始状态为0
// 在字符串中匹配
for (int i = 0; i < N; i++) {
j = dp[j][s[i]];
// 如果状态到达模式串尾部，说明匹配成功
if (j == M) return i - M + 1;
}
return -1;
}
int main() {
string s, p;
while (cin >> s >> p) {
cout << search(s, p) << endl;
}
return 0;
}
最后一个单词的长度
给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。
输入：字符串
输出：最后一个单词的长度
思路：分别寻找边界
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
while (getline(cin, s)) {
int r = s.size() - 1;
while (r > 0 && s[r] == ' ') r--;
int l = r;
while (l > 0 && s[l] != ' ') l--;
cout << r - l << endl;
}
return 0;
}
字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
输入：一组字符串。
输出：对他们的分组
思路：利用哈希表 关键是对他们实施一个标准，这儿采用排序作为他们的键。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<string> strs;
string s;
while (cin >> s) {
strs.push_back(s);
}
unordered_map<string, vector<string>> hash;
// 关键是构建一个标准作为他们的键 这儿选择对他们进行排序
for (auto str : strs) {
string key = str;
sort(key.begin(), key.end());
hash[key].push_back(str);
}
vector<vector<string>> res;
for (auto item : hash) {
res.push_back(item.second);
}
for (int i = 0; i < res.size(); i++) {
for (auto s : res[i]) {
cout << s;
}
cout << endl;
}
return 0;
}
字符串相乘
给定两个以字符串形式表示的非负整数 s1 和 s2，返回 s1 和 s2 的乘积，它们的乘积也表示为字符串形式。
输入：两个数字字符串
输出：两个字符串的乘积
思路：模拟题。注意代码的写法技巧
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
string add(string s1, string s2) {
string res = "";
int carry = 0;
// 注意这儿代码的写法 技巧
for (int i = s1.size() - 1, j = s2.size() - 1; i >= 0 || j >= 0 || carry;
i--, j--) {
int n1 = i < 0 ? 0 : s1[i] - '0';
int n2 = j < 0 ? 0 : s2[j] - '0';
int sum = (n1 + n2 + carry) % 10;
carry = (n1 + n2 + carry) / 10;
res = to_string(sum) + res;
}
return res;
}
int main() {
string s1, s2;
while (cin >> s1 >> s2) {
string res = "0";
for (int i = s2.size() - 1; i >= 0; i--) {
string t = "";
int carry = 0;
// 补零操作
for (int j = s2.size() - 1; j > i; j--) {
t += '0';
}
int n2 = s2[i] - '0';
// 相乘操作
for (int j = s1.size() - 1; j >= 0 || carry != 0; j--) {
int n1 = j < 0 ? 0 : s1[j] - '0';
int mul = (n1 * n2 + carry);
t = to_string(mul % 10) + t;
carry = mul / 10;
}
res = add(t, res);
}
cout << res << endl;
}
return 0;
}
通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。
- ’?’ 可以匹配任何单个字符
- ‘*’ 可以匹配任意字符串(包括空字符串)
输入：一个字符串和一个模式串
输出： 两个字符串是否匹配
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, p;
while (cin >> s >> p) {
vector<vector<bool>> dp(s.size() + 1,
vector<bool>(p.size() + 1, false));
// base case 空字符串匹配的情况
dp[0][0] = true;
// 模式串匹配空字符串的情况
for (int i = 0; i < p.size(); i++)
dp[0][i + 1] = p[i] == '*' && dp[0][i];
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < p.size(); j++) {
// 如果当前字符匹配
if (s[i] == p[j] || p[j] == '?')
dp[i + 1][j + 1] = dp[i][j];
// 如果当前字符是 * 时
else if (p[j] == '*')
dp[i + 1][j + 1] = dp[i][j] || dp[i][j + 1] || dp[i + 1][j];
}
}
cout << dp[s.size()][p.size()] << endl;
}
return 0;
}
单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
- 拆分时可以重复使用字典中的单词
- 可以假设字典中没有重复的单词
输入：一个字符串和一个单词字典
输出：能否拆分
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
// 暴力深搜
bool dfs(string s, unordered_set<string> dict, int begin) {
if (begin == s.size()) return true;
for (int i = begin; i < s.size(); i++) {
if (dict.find(s.substr(begin, i - begin + 1)) != dict.end() &&
dfs(s, dict, i + 1))
return true;
}
return false;
}
// 备忘录式深搜
bool dfs2(string s, unordered_set<string> dict, int begin, vector<int>& memo) {
if (begin == s.size()) return true;
if (memo[begin]) return memo[begin] > 0;
for (int i = begin; i < s.size(); i++) {
if (dict.find(s.substr(begin, i - begin + 1)) != dict.end() &&
dfs2(s, dict, i + 1, memo)) {
memo[begin] = 1;
return true;
}
}
memo[begin] = -1;
return false;
}
int main() {
string s;
cin >> s;
string w;
unordered_set<string> dict;
while (cin >> w) {
dict.insert(w);
}
// 动态规划
vector<bool> dp(s.size() + 1,
false); // 表示字符串前i个字符是否可以拆分成单词表中单词
dp[0] = true;
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
dp[i] = true;
break;
}
}
}
cout << dp[s.size()] << endl;
// 深搜
cout << dfs(s, dict, 0) << endl;
// 备忘录式深搜
vector<int> memo(s.size(), 0); // 0是未被访问 1是可以，-1是不可以
cout << dfs2(s, dict, 0, memo) << endl;
return 0;
}
串联所有单词的子串
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
输入：一个字符串和一个单词字典
输出：输出匹配位置的起点
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
unordered_map<string, int> word;
string w;
while (cin >> w) word[w]++;
int wordlen = w.size();
int len = word.size() * wordlen;
for (int i = 0; i < s.size() - len + 1; i++) {
unordered_map<string, int> window;
int nums = 0;
while (nums < word.size()) {
string t = s.substr(i + nums * wordlen, wordlen);
if (!word.count(t)) break;
if (window.count(t) && window[t] + 1 <= word[t])
window[t]++;
else
break;
nums++;
}
if (nums == word.size()) cout << i << endl;
}
return 0;
}
至少有k个重复字符的最长子串
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
输入：字符串和K值
输出：满足要求的最长子串
思路：先用hash表统计s中每个字符出现的次数，显然如果字符c出现的次数小于k，c必然不在最长子串里面，根据这个特性可以将原始s分割成多个子串递归地求解问题，我们用一个split数组依次来存放每个分割点的索引，对每个分割区间同样求解该问题(多路的分治问题)，并取结果的最大值保存在变量ans中，此处有一个小trick（如果当前求解的子串长度比已存在的ans还要小，则没有必要求解该区间，这样可以减少不必要的计算），最后递归的结束点就是当前求解的字符串s符合最长子串的要求。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int helper(string s, int k) {
unordered_map<char, int> hash;
for (auto c : s) hash[c]++;
vector<int> split;
for (int i = 0; i < s.size(); i++) {
if (hash[s[i]] < k) split.push_back(i);
}
if (split.size() == 0) return s.size();
int res = 0, l = 0;
split.push_back(s.size());
for (int i = 0; i < split.size(); i++) {
int len = split[i] - l;
if (len > res) res = max(res, helper(s.substr(l, len), k));
l = split[i] + 1;
}
return res;
}
int main() {
string s;
while (cin >> s) {
int k;
cin >> k;
cout << helper(s, k) << endl;
}
return 0;
}
