本文针算法题中常见的子字符串类型题目，总结一种较为通用的方法，并以三个题目进行讲解。
LeetCode 76. Minimum Window Substring（最小覆盖子串）
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"Note:
- If there is no such window in S that covers all characters in T, return the empty string
"".- If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
题目要求：给一个字符串S和目标字符串T，找到S的最短子字符串要求包含T中所有字符。
思路：用map记录T中各个字符出现的次数，用counter记录T中总的字符数。从头开始遍历字符串，维护一个动态窗口，began指向窗口起始位置，end指向窗口结束位置。counter用我们用一个map记录窗口中的字符是否存在于T，由于T中字符可能存在重复，因此对于字符的计数是有必要的。遍历时，end指针右移，判断该位置字符是否存在于T，若是并且map中该字符对应的计数大于零，则map中该字符计数减一，counter减一（表示T中该字符被找到了一个，下面的任务是找到剩下的counter个字符）。当counter==0，说明T中所有的字符全被找到了，此时的窗口表示的字符串是一个有效的字符串，若比之前找到的有效字符串更短，则将head指向began，d更新为更端的长度。同时，我们判断此时的began处的字符在map中的计数，如果为负，则说明这个字符已经被减了多次（在窗口中冗余了，多出了我们需要的个数），那began可以直接右移一位，map中的计数加一（表示这个字符被踢出计数范围了）；如果为0，说明窗口中该字符的个数不多不少，正是我们所需要的个数，因为我们需要寻找新的有效字符串，将began右移后，map中该计数加一，counter也要加一（表示现在那个有效的字符被踢出了现在需要寻找另一个一样的字符替换它）。遍历完就可以使用我们记录的头指针head和最短长度d返回结果了。
class Solution{
public String minWindow(String s, String t) {
int head = 0, begain = 0, end = 0, counter = t.length();
int d = Integer.MAX_VALUE;
HashMap<Character, Integer> map = new HashMap<>();
for(char c : t.toCharArray()){
map.put(c, map.getOrDefault(c, 0) + 1);
}
while(end < s.length()){
if(map.containsKey(s.charAt(end))){
map.put(s.charAt(end), map.get(s.charAt(end)) - 1);
if(map.get(s.charAt(end)) > -1)
counter--;
}
end++;
while(counter == 0){
if(d > end - begain) d = end - (head = begain);
if (map.containsKey(s.charAt(begain))){
map.put(s.charAt(begain), map.get(s.charAt(begain)) + 1);
if(map.get(s.charAt(begain)) > 0) counter++;
}
begain++;
}
}
if(d != Integer.MAX_VALUE) return s.substring(head, head + d);
else return "";
}
}
这里面有个简化的地方。
上面的map中记录的全部是在目标字符串中出现的字符。这就导致我们每次滑动end指针和began指针时都要判断它是否是T中的字符，从而决定是否要对map进行加一或减一。比如在内循环while中，当我们判断了它是T中的字符，我们要对map中计数加一，当加一后若大于0，说明began滑动后这个缺失了，counter要加一，以使当前窗口表示的字符无效，并寻找新的字符。也就是说counter每次是根据map相应位置的计数判断是否改变的，那么我们能不能在遍历的时候直接将非T中的字符也放入map呢？答案是肯定的，因为非T中字符在窗口中总是冗余的，所以存入map，map中的计数总是为负，也表示冗余状态，这个判断出这个状态就无需对counter进行修改。因此我们就简化了每次对滑动处的字符的判断。代码如下：
class Solution{
public String minWTindow(String s, String t) {
int head = 0, began = 0, end = 0, counter = t.length();
int d = Integer.MAX_VALUE;
HashMap<Character, Integer> map = new HashMap<>();
for(char c : t.toCharArray()){
map.put(c, map.getOrDefault(c, 0) + 1);
}
while(end < s.length()){
map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) - 1);
if(map.get(s.charAt(end)) > -1)
counter--;
end++;
while(counter == 0){
if(d > end - began) d = end - (head = began);
map.put(s.charAt(began), map.get(s.charAt(began)) + 1);
if(map.get(s.charAt(began)) > 0) counter++;
began++;
}
}
if(d != Integer.MAX_VALUE) return s.substring(head, head + d);
else return "";
}
}
我们可以总结一个解决子字符串类型题目的模板，如下：
class Solution{
public String minWTindow(String s, String t) {
int counter; // 用于判断此时的窗口是否是有效子字符串
int began = 0, end = 0; // 两个指针，标记窗口的始末位置
int head = 0; // 最优有效子字符串的起使位置
int d; // 最优有效子字符串的长度
HashMap<Character, Integer> map = new HashMap<>(); // 字符计数器
for(){
// 初始化字符计数器
}
while(end < s.length()){
map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) - 1);
if(map.get(s.charAt(end)) > -1)
// 修改counter
end++; // 滑动end指针
while( /*counter状态判断*/ ){
if( /*d：最优结果判断条件*/) d = ..; // 更新最优结果
map.put(s.charAt(began), map.get(s.charAt(began)) + 1);
if(map.get(s.charAt(began)) > 0) ..; // 修改counter
began++; // 滑动began指针
}
}
if(d != Integer.MAX_VALUE) return s.substring(head, head + d);
else return "";
}
}
好了，我们现在尝试用这个方法做一个简单点的题目。
LeetCode 3.Longest Substring Without Repeating Characters（无重复字符的最长子串）
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.Example 2:
Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.Example 3:
Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
题目要求：给一个字符串，寻找最长不含重复字符的子字符串。
思路：维护一个滑动窗口，map记录字符个数，counter初始为0，表示窗口是否是有效子字符串，大于0，说明有重复，需要滑动began，消除重复。遍历字符串，将end指针所指的字符放入map（相应位置加一），如果该字符计数大于一，就说明有重复了，counter加一。若counter大于0，说明有重复，滑动began。
只返回最长不含重复字符的子字符串长度，代码如下：
class Solution{
public int lengthOfLongestSubstring(String s) {
int begain = 0, end = 0, d = 0;
HashMap<Character, Integer> map = new HashMap<>();
int counter = 0;
while (end < s.length()) {
map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) + 1);
if(map.get(s.charAt(end)) > 1) counter++;
end++;
while (counter > 0) {
map.put(s.charAt(begain), map.get(s.charAt(begain)) - 1);
if(map.get(s.charAt(begain)) >= 1) counter--;
begain++;
}
d = Math.max(d, end - begain);
}
return d;
}
}
返回最长不含重复字符的子字符串，代码如下：
class Solution{
public String LongestSubstring(String s) {
int began = 0, end = 0, d = 0;
int head = 0;
HashMap<Character, Integer> map = new HashMap<>();
int counter = 0;
while (end < s.length()) {
map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) + 1);
if(map.get(s.charAt(end)) > 1) counter++;
end++;
while (counter > 0) {
map.put(s.charAt(began), map.get(s.charAt(began)) - 1);
if(map.get(s.charAt(began)) >= 1) counter--;
began++;
}
if(d < end - began) d = end - (head = began);
}
return s.substring(head, d);
}
}
我知道你可能有别的方法，但使熟练使用这种方法后，是不是思路会更清晰呢。
就做两个题，可能离熟练还差点意思，那再来一道。
Longest Substring with At Most Two Distinct Characters
题目要求：寻找只包含两个不同字符的最长子字符串，比如输入：”abddcccffffee"，结果就是“cccffff”。
代码如下：
class Solution{
public String longestSubstring2(String s){
int began = 0, end = 0, counter = 0; // 记录窗口中不同的字符有多少个
int head = 0, d = Integer.MIN_VALUE; // 记录最优子字符串的起始位置和长度
HashMap<Character, Integer> map = new HashMap<>();
while (end < s.length()) {
map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) + 1);
if (map.get(s.charAt(end)) == 1) counter++; // 当新加入的字符计数为1，则表明这是个"新成员”，需要跟新counter
end++;
while (counter > 2){ // 当counter超过2，字符无效，就要滑动began使字符重新变得有效
map.put(s.charAt(began), map.get(s.charAt(began)) - 1);
if(map.get(s.charAt(began)) <= 0) counter--;
began++;
}
// 这里需要注意！
// 更新最优子字符串需要在内层while循环后，而不是内部，因为内部窗口还不是有效的子字符串（不同的字符超过2）
if(d < end - began) d = end - (head = began);
}
if(d != Integer.MIN_VALUE) return s.substring(head, head + d);
else return "";
}
}
