Leetcode | 第C节：字符串综合题（2）
————————————————————————————————————
大家好！
东京奥运会圆满收官！当然我自己也将迎来留学前的最后准备，所以更新速度可能还是会比较慢……但还好，大部分的内容都已经在之前写的差不多了，也希望最后这几篇我也能够尽快更完，当然也希望大家可以谅解～
这一节我们开始介绍一些字符串相关的综合题。和数组不同的地方在于，字符串的处理方式有自己独特的一套api，这当然也是我们需要学习和掌握的内容。
那么我们开始吧。
字符串综合题
Problem 1: Leetcode 451 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
比方说如果输入是"tree"，那么输出就是"eert"，这里的'e'出现了2次，其他的字符都是1次。
这个问题从算法角度上来说是没有任何难度的。先按照顺序对字符串进行遍历，然后用哈希表存储频率，最后按照这个频率排序即可。这一个题的目的主要是在一开始，先熟悉一些字符串相关题目专属的api，也算是一个过渡。
好的，我们直接看代码。
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> mp; // 创建哈希表
int length = s.length();
for (auto &ch : s) {
mp[ch]++; // 枚举每一个字符的出现频率
}
vector<pair<char, int>> vec;
for (auto &it : mp) {
vec.emplace_back(it); // 将频率放入vector中，这是为了排序，哈希表本身是没有顺序的。
}
sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
return a.second > b.second; // 对量级进行排序
});
string ret;
for (auto &[ch, num] : vec) {
for (int i = 0; i < num; i++) {
ret.push_back(ch); // string也可以进行push_back，相当于在后端直接拼接。
}
}
return ret;
}
};
类似的模拟类型的题目还有Leetcode 38等。
Problem 2: Leetcode 316 给你一个字符串
s，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
比方说如果输入是s = "bcabc"，那么输出就是"abc"，可以看到确实有一个子字符串"abc"，并且很明显它是字典序最小的。
对于这个问题其实很容易发现，因为我们要找的是“字典序最小的”，且不能重复，那么很明显，一个单调上升的字符串肯定是必要的（想想为什么？）。这个情况促使我们想到单调栈这个做法。
我们在这里再复习一下单调栈的具体做法。
当遇到新字符的时候，比较它与栈顶元素的大小。如果比栈顶元素小（这里指的是字符的ascii码，也就对应字典序），那么就应该出栈，一直到新元素比栈顶元素大了，再入栈。
出栈的关键在于，假如说栈顶元素是
，出栈的元素是
，那么如果
，说明如果入栈的话，就是之后的元素要比之前的元素小，相当于一个逆序，我们之前说过，单调上升的字符串才有可能是字典序最小的，所以这是矛盾的。因此我们要一直出栈直到
满足才可以。而且正是因为我们维护了一个单调上升的序列，这个做法才叫作单调栈。
但是这里要注意，我们有“不重复”的制约，因此也不能够乱来。这里的关键在于，我们是为了“去重”，所以一方面，新的字符如果已经在栈中存在，那么这个时候，就不能再次将这个元素入栈了。另一方面，如果已有的栈顶元素不满足要求，但是之后的所有字符里都没有和它一样的了，那么这个时候也不可以出栈。因为如果出栈，虽然确实不会有重复的，但是答案中并没有包含所有的字符串，因此也不是正确答案。
好的，我们来看一下代码吧。
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> vis(26), num(26);
for (char ch : s) {
num[ch - 'a']++; // 记录每一个字符的数量。
}
string stk;
for (char ch : s) {
if (!vis[ch - 'a']) { // 如果栈中已经存在这个元素，那么无论如何也不能够再入栈
while (!stk.empty() && stk.back() > ch) {
if (num[stk.back() - 'a'] > 0) { // 如果数量为0，不能出栈
vis[stk.back() - 'a'] = 0;
stk.pop_back();
} else {
break;
}
}
vis[ch - 'a'] = 1; // 标记栈中存在了这个元素
stk.push_back(ch);
}
num[ch - 'a'] -= 1; // 枚举了一个，就要对应字符数量-1
}
return stk;
}
};
当然了，其实这个说法/做法也是不严谨的，我们要加上这么一个条件，才能说是一个严谨的做法。
给定一个字符串
ss，如何去掉其中的一个字符ch，使得得到的字符串字典序最小呢？答案是：找出最小的满足s[i]>s[i+1]的下标i，并去除字符s[i]。
读者可以自己想想这个命题的准确性，当然了本质上这其实也是一个贪心的策略，而且正确（证明我们就不写了）。当然了，还需要思考的问题是，为什么单调栈的策略可以保证，一定可以每一步都完成这个命题所需要做的事情。
关于单调栈其他方面的问题，可以看一下这一篇文章。
Problem 3: Leetcode 556 给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。 注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。
比方说如果输入n = 12，那么输出就是21。
这个问题其实还是有点难度的，我们一步步推进。首先一个降序的排列不可能可以找到更大的排列。所以我们可以得到的结论是，如果一个数字的右边排序是降序，那么可以固定这个元素，然后找一个比它更大的元素先去替代它（我们一会儿再解释这么做的idea是什么）。
所以总结一下，假如说我们找到了一个位置（不妨设为
），它的之后的元素是降序的。那么我们首先从右往左，在这个数字的每一位中，寻找大于这个元素本身，但是只是“刚好大一点”的一个元素
（相当于在所有大于
的元素中的最小的那个），然后交换这两个元素的顺序。在这之后，把这个位置及其之后元素所组成的序列再排一个升序就可以了。
举一个例子，假如说一开始的元素是12321，那么容易看出，下一个最大的元素是13122。首先，我们找到了这个位置，是从左往右数的第二个（对应2），然后我们就可以找，用哪一个元素可以与这个2交换。很明显，是3。交换之后，数字变成了13221，那么就只需要再把最后三位排成升序就可以了。
现在我们简单说一下这个想法的idea。首先降序肯定没办法更大了，所以就需要在降序之前一位找法子（因为你不能再往前移动位置，去改变对应位置的数字了，那样的话数字就会变得更大，不符合”下一个“更大的元素。同样你也不能往后移动，因为是降序，没招）。很明显，如果是要下一个排列的话，我们就必须要找这个“刚好大一点点”的数字。而且对应后面的位数必定会变成升序排列。就比方说全排列中，1432的下一个就是2134，也是满足了我们之前提到的要求。当然，如果你想到了全排列的构造方式，这个idea也是很自然的。
好的，我们来看看代码吧。
public class Solution {
public int nextGreaterElement(int n) {
char[] a = ("" + n).toCharArray();
int i = a.length - 2;
while (i >= 0 && a[i + 1] <= a[i]) {
i--; // 从右往左，找到第一个符合条件的位置，这个位置之后的排列都是降序的。
}
if (i < 0)
return -1; // 完全降序，那不可能找到下一个
int j = a.length - 1;
while (j >= 0 && a[j] <= a[i]) {
j--; // 找到第一个“刚刚大一点”的元素，这里注意顺序是从右往左，也是为了考虑到改变后对应数字大小的改变。
}
swap(a, i, j);
reverse(a, i + 1); // 注意，这是自定义的函数，在下面
try {
return Integer.parseInt(new String(a));
} catch (Exception e) {
return -1; // 注意题目有额外的对于32位数字的要求。
}
}
private void reverse(char[] a, int start) {
int i = start, j = a.length - 1;
while (i < j) {
swap(a, i, j);
i++;
j--; // 这是因为一开始的数字一定是降序的，所以这种修改方式可以把它变成升序。当然，你也可以使用排序的api。
}
}
private void swap(char[] a, int i, int j) {
char temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
当然了这个代码是用Java写的。
Problem 4: Leetcode 395 给你一个字符串
s和一个整数k，请你找出s中的最长子串， 要求该子串中的每一字符出现次数都不少于k。返回这一子串的长度。
比方说如果我们有s = "ababbc", k = 2，那么答案就是5，这里对应的字符串就是"ababb"，注意如果带上'c'，因为我们要求了每一个字符都要出现至少k次，所以是不符合要求的。
对于这个问题，我们抓住关键词：连续子串，所以最容易想到的做法就是滑动窗口。简单来说，我们固定了一个数
，表示我们的字符种类个数（比方说"aabb"对应有2种字符，所以t = 2，这只是为了枚举方便）。然后我们考虑一下，选择滑动窗口的左右边界
，然后我们可以先把
设置为最右边，然后枚举
，目标是
这个区间内的字符串，它的字符种类个数不超过我们设置的
。那么很明显，一定可以找到这样的一个临界点
，满足
更小的话，字符种类个数不满足要求，更大的话，又不满足“最长子串”的要求。
关于
，我们自然就是要求满足题目的条件了。这个
可以一开始把
设置为最右边，然后向左移动
，一直到满足条件为止。
问题在于如何统计区间内的每一个元素所出现的次数。当然我们也可以考虑每一次都枚举统计一下区间内的各个元素的出现次数，但这样会浪费很多时间。一个好的法子是设计一个计数器
，记录当前的出现次数小于
的字符数量。那么实际上只会对应两种情况。
- 当某个字符的出现次数从0增加到1时，将
加一；
- 当某个字符的出现次数从k-1增加到k时，将
减一。
注意这个“某个字符”就是你当前枚举所遇到的字符。读者可以自己思考为什么这样就可以。当然了，只有
才是符合要求的。所以我们可以把
不断地左移，来完成我们的目标。
所以对于每一个
，我们都可以找到一个
和
。在这里取到一个最大值即可。我们这里直接给出代码。
class Solution {
public:
int longestSubstring(string s, int k) {
int ret = 0;
int n = s.length();
for (int t = 1; t <= 26; t++) {
int l = 0, r = 0;
vector<int> cnt(26, 0);
int tot = 0;
int less = 0;
while (r < n) { // 这一步是为了统计less和tot（对应字符种类个数），同时把r移到最右边
cnt[s[r] - 'a']++;
if (cnt[s[r] - 'a'] == 1) {
tot++;
less++;
}
if (cnt[s[r] - 'a'] == k) {
less--; // 根据条件更改less
}
while (tot > t) { // 更改l的位置
cnt[s[l] - 'a']--;
if (cnt[s[l] - 'a'] == k - 1) {
less++;
}
if (cnt[s[l] - 'a'] == 0) {
tot--;
less--;
}
l++;
}
if (less == 0) {
ret = max(ret, r - l + 1); // 统计最大的字符串长度
}
r++;
}
}
return ret;
}
};
这个题还有个算法是分治算法，不过我们这里节省时间，就先不说了。读者可以自己看一下官方的题解。
Problem 5: Leetcode 151 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
比方说如果输入是s = "the sky is blue"，那么输出就是"blue is sky the"，注意这里的翻转不是翻转单词内部的字母顺序。
这一个问题本身也确实是没什么算法可言，就是一个纯模拟题。同样，这个问题的目的也是让大家熟悉一下api。
对于这个问题，做法也很多，但都是很朴素的模拟。我们这里贴出一种不会使用太多简便api的方式。
class Solution {
public:
string reverseWords(string s) {
// 反转整个字符串
reverse(s.begin(), s.end());
int n = s.size();
int idx = 0;
for (int start = 0; start < n; ++start) {
if (s[start] != ' ') {
// 填一个空白字符然后将idx移动到下一个单词的开头位置
if (idx != 0) s[idx++] = ' ';
// 循环遍历至单词的末尾
int end = start;
while (end < n && s[end] != ' ') s[idx++] = s[end++];
// 反转整个单词
reverse(s.begin() + idx - (end - start), s.begin() + idx);
// 更新start，去找下一个单词
start = end;
}
}
s.erase(s.begin() + idx, s.end());
return s;
}
};
这里的本质就是第一件事，整个字符串翻转，第二件事，再将每一个单词内部做翻转。读者可以自己模拟一遍，看为什么这就是我们要的答案。
当然了，如果是使用Python的，那么会发现这道题的一个更加简便的方法。不过这里我们就不多提了。
Problem 6: Leetcode 516 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
比方说如果输入是s = "bbbab"，那么输出就是4。因为你可以从中抽出一个"bbbb"出来，这个是最长的回文子序列。
注意这里并没有要求一个“连续子串”，只是子序列。所以其实可以考虑使用动态规划的方法。考虑设f[i][j]为区间
中，可以组成的最长回文序列的长度。那么很明显，关键点就是在于边界的两个元素。
具体来说，我们可以考虑一下，如果要求一个子序列是回文的，那么必须要求的是两边的字符一致。所以分开来看，如果
两个位置的字符相同，那么这个时候就只需要考虑区间
的情况了，这个时候对应的状态转移方程就是
。
但是如果是不相同呢？这个时候很明显，这个回文子序列不可能同时包含
两个位置的字符。所以我们就把它倒退到
中的一个就可以。
最后就是边界情况，这个问题的边界情况还是很好处理的，即区间长度只有1的情况。这个时候相当于只有一个字符，那它本身当然是一个回文串。
好的，我们来看看代码吧。
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] f = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
f[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) { // 这是java访问字符串对应位置的api
f[i][j] = f[i + 1][j - 1] + 2;
} else {
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
}
}
}
return f[0][n - 1];
}
}
当然了，如果寻找的不是回文的子序列，而是子串（对应Leetcode 516），那么我们其实也可以通过中心拓展算法来寻找。不过这个算法难度也不大，作为一个单独的题目来说又有点太占篇幅了，所以我们就没单独说，但还是推荐大家去看一下这一个题目。
Problem 7: Leetcode 115 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是） 题目数据保证答案符合 32 位带符号整数范围。
比方说输入是s = "rabbbit", t = "rabbit"，那么输出就是3，因为你可以在s中找到3个含有t的字符串。
这一个问题还是有些困难的，同样它也是我们前面提到过的子序列的问题，所以这一个题我们第一反应，应该也是使用动态规划来求解的。
如果要在
中找到一个子序列它碰巧是
，自然的思路就是把
都拆分开考虑。所以我们的状态dp[i][j]可以设置为
的子序列中，
出现的次数，这里的
表示从位置
出发一直到字符串最后的这一段子串。
所以有了这个假设，问题就好解决了。我们只需要考虑
这两个情况。事实上，如果
，那么根据排列组合，可以有两个选择。可以选择让
和
匹配，也可以不匹配。匹配的话，只需要关心
的匹配情况，这个时候对应的是
。不匹配的话，相当于考虑
只作为
的子序列，这个时候对应的是
。
但是如果
，这个时候就只能选不匹配了。那么对应的答案就是
。
总结一下，我们可以得到这样的状态转移方程。
当然这里的边界条件也需要多思考一下。首先，
如果是空的字符串（对应
，
是字符串
的长度，下类似），那么自然它肯定是任何字符串的子序列，所以
。但如果
是空字符串，但是
不是，这个时候就没有办法做任何的匹配，对应的是
。
那么我们来看看代码吧。
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.length(), n = t.length();
if (m < n) {
return 0;
}
vector<vector<long>> dp(m + 1, vector<long>(n + 1));
for (int i = 0; i <= m; i++) {
dp[i][n] = 1;
}
for (int i = m - 1; i >= 0; i--) {
char sChar = s.at(i);
for (int j = n - 1; j >= 0; j--) {
char tChar = t.at(j);
if (sChar == tChar) {
dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
} else {
dp[i][j] = dp[i + 1][j];
}
}
}
return dp[0][0];
}
};
Problem 8: Leetcode 49 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。
所以比方说"eat"和"tea"就是一组字母异位词，但是"bat"和"eat"就不是，因为所含的字母不一样。
这一个问题的处理方式也不难想，官方提供了两个思路。一个是考虑将每一个单词按照升序/降序排列，这样的话字母异位词一定会最终得到相同的形式。另外一个则是对每一个单词，统计它每一个字母对应的频数。这里我们主要用前者的思路。
既然要统计字母异位词，我们就可以使用哈希表来进行存储。简单来说，排序之后的单词我们作为哈希表的key，而它的value就是一个列表，用来存储所有的字母异位词相同的单词。所以对应的代码也很好写，只要你熟悉一些常见的api的话。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
Problem 9: Leetcode 76 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。
比方说如果输入是s = "ADOBECODEBANC", t = "ABC"，那么输出就是"BANC"。这是包含t中所有字符的子串，并且它是最短的那个。
熟悉的感觉回来没？是的，这是一个与子串，也就是之前的连续子数组相关的问题。因此，我们可以想到上一节所说的，滑动窗口的方法。简单来说，我们给定左右指针
，分别一开始表示字符串的最左边和最右边。然后我们第一步先移动右指针
，一直到子串包含了所有的
中的字符。然后再移动
，一直到
不能够移动为止。每一次这样的“先移动
，再移动
“循环，我们都可以得到一个“可能的长度最小的”满足条件的子串。然后我们可以再把
向右移动1格，重复这样的操作，一直到
到达最右边为止。
好的，我们来看一下代码吧。
class Solution {
public:
unordered_map <char, int> ori, cnt;
bool check() {
for (const auto &p: ori) {
if (cnt[p.first] < p.second) {
return false;
}
}
return true;
}
string minWindow(string s, string t) {
for (const auto &c: t) {
++ori[c];
}
int l = 0, r = -1;
int len = INT_MAX, ansL = -1, ansR = -1;
while (r < int(s.size())) {
if (ori.find(s[++r]) != ori.end()) {
++cnt[s[r]];
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
}
if (ori.find(s[l]) != ori.end()) {
--cnt[s[l]];
}
++l;
}
}
return ansL == -1 ? string() : s.substr(ansL, len);
}
};
小结
其实我们还有一些小的字符串的题目还没有放出来，我们会把它和下一节的相关问题放在一起，做一个单独的一节内容。可以看出，对于字符串的相关内容，其实也没有特别多独特的算法或数据结构的知识，也只是把我们之前介绍的知识搬过来用了而已。
在下一节，我们也会把剩下的一部分字符串相关的题目列出来，并且介绍一些新的，像贪心，位运算，字典树等相关的算法与数据结构相关的问题。