1.无重复字符的最长子串（3 - 中/剑指48）
题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 :
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
思路：本题是面试的高频题目，也是hash表的一个具体应用。思路是维持一个队列（窗口），保持队列中的元素满足题目要求（元素不重复）。
具体实现是：使用hashmap记录每个字符的索引位置，便于更新下一个窗口的左边界，遍历字符串。
- 如果窗口中含有这个元素，移动移除左边界元素（左边索引+1）；
- 否则加入窗口，更新最长子串长度。
代码实现：
public int lengthOfLongestSubstring(String s) { int n = s.length(); if (s == null || n == 0) { return 0; } Map<Character, Integer> map = new HashMap<>(); int max = 0; int left = 0; for (int i = 0; i < n; ++i) { char c = s.charAt(i); if (map.containsKey(c)) { left = Math.max(left, map.getOrDefault(c, 0) + 1); } map.put(c, i); max = Math.max(max, i - left + 1); } return max; }
2.串联所有单词的子串（30 - 难）
题目描述：给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意：子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 :
输入： s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9] 解释： 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。
思路：由于单词长度固定，我们维护一个长度为所有元素长度总和的队列（窗口）。本题也是考察hash表，键为存储的单词，值存的单词出现的次数。具体实现见代码。注意：
- 可以用indexOf()，判断一个字符或者字符串是否存在一个字符串中，不存在返回负数；否则将这个单词加入哈希表；
- 当单词数组长度超过字符串长度，直接剔除。
- 对遍历的每一个窗口，用一个subMap记录，left和right记录左右边界（更新的话，是先将单词从字符串中截取出来，再在subMap中删除）；
- 通过移动右边界right，依次得到一个单词。如果wordMap中没有这个单词，更新左边界，清除这次记录（包括subMap和单词数量记录数count）；否则，加入subMap，注意count符合要求统计左边界，超过限制删除左边界。
代码实现：
public static List<Integer> solution2(String s, String[] words) { List<Integer> res = new ArrayList<>(); Map<String, Integer> wordsMap = new HashMap<>(); if (s.length() == 0 || words.length == 0) return res; for (String word: words) { // 主串s中没有这个单词，直接返回空 if (s.indexOf(word) < 0) return res; wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1); } int oneLen = words[0].length(), wordsLen = oneLen * words.length; if (wordsLen > s.length()) return res; for (int i = 0; i < oneLen; ++i) { int left = i, right = i, count = 0; // 统计每个符合要求的word Map<String, Integer> subMap = new HashMap<>(); // 右窗口不能超出主串长度 while (right + oneLen <= s.length()) { // 得到一个单词 String word = s.substring(right, right + oneLen); right += oneLen; // words[]中没有这个单词，那么当前窗口肯定匹配失败，直接右移到这个单词后面 if (!wordsMap.containsKey(word)) { left = right; subMap.clear(); count = 0; } else { subMap.put(word, subMap.getOrDefault(word, 0) + 1); ++count; // 如果这个单词出现的次数大于words[]中它对应的次数，又由于每次匹配和words长度相等的子串 // 如 ["foo","bar","foo","the"] "| foobarfoobar| foothe" // 第二个bar虽然是words[]中的单词，但是次数抄了，那么右移一个单词长度后 "|barfoobarfoo|the" // bar还是不符合，所以直接从这个不符合的bar之后开始匹配，也就是将这个不符合的bar和它之前的单词(串)全移出去 while (subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0)) { // 从当前窗口字符统计map中删除从左窗口开始到数量超限的所有单词(次数减一) String w = s.substring(left, left + oneLen); subMap.put(w, subMap.getOrDefault(w, 0) - 1); // 符合的单词数减一 --count; // 左窗口位置右移 left += oneLen; } // 当前窗口字符串满足要求 if (count == words.length) res.add(left); } } } return res; }
3.最小覆盖子串（76 - 难）
题目描述：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。要求：时间复杂度O(N)。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案，两个字符串只含有英文字符。
示例 :
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC"
思路：可以通过滑动窗口解决，注意：最小覆盖子串长度不唯一，但至少与t相同。我们可以定义两个变量：start（最小覆盖子串的起始位置），size（最小覆盖子串的长度）
关键：如何判断窗口中含有t的所有元素？可以使用数组或者哈希表记录字符出现的次数。
- 使用数组记录t中（我们需要寻找的）字符的个数，cnt记录要找字符总数。
- 当我们遍历s字符串时，遇到需要的字符我们就将他出现的次数 - 1。总次数cnt == 0，此时找到一个覆盖子串。
- 上述还不是一次寻找的最小覆盖子串，需要找左边界，如何找呢？还是通过出现的次数，方法：在遍历过程中，s中出现每个的字符在need数组中-1，这样我们在找左边界是为负数，一定要恢复！
- 这时，可以统计长度size，更新起始索引start；
- 最终，移动窗口，如何移动（删除左边界元素）呢？将其加入need数组，更新左边界和cnt个数 + 1，下次遍历出现这个字符就可以删除（也可以理解为替换）。
代码实现：
public String minWindow(String s, String t) { if (s == null || s.length() == 0 || t == null || t.length() == 0 || s.length() < t.length()) { return ""; } // 记录需要字符的个数 int[] need = new int[128]; for (int i = 0; i < t.length(); i++) { need[t.charAt(i)]++; } int left = 0; int size = Integer.MAX_VALUE, cnt = t.length(); int start = 0; for (int i = 0; i < s.length(); i++) { if (need[s.charAt(i)] > 0) cnt--; need[s.charAt(i)]--; // 窗口中已经包含所有需要的字符 if (cnt == 0) { while (left < i && need[s.charAt(left)] < 0) { need[s.charAt(left)]++; left++; } if (i - left + 1 < size) { size = i - left + 1; start = left; } // 窗口移动，注意更新need数组和cnt值 need[s.charAt(left)]++; left++; cnt++; } } return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size); }
4.找到字符串中所有字母的异位词（438 - 中）
题目描述：
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 :
输入: s: "cbaebabacd" p: "abc" 输出: [0, 6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
思路：显然滑窗，窗口大小为p字符串的长度，关键：那么如何比较两部分的元素是否是异位词呢？
- 可以直接调库函数
Arrays.equals()，判断两个字符串是否是异位词（即两个数组是否相同）。 - 本题仍使用数组存储字符出现次数，但是本题两个串申请了两个空间，方便进行上边的对比。
- 这里判断与上题相比简单了许多，只要长度满足我们就进行判断，两部分异构，记录起始索引；否则，移除左边界，这里直接在sMap删除。
代码实现：
public List<Integer> findAnagrams(String s, String p) { List<Integer> ans = new ArrayList<>(); if (s.length() < p.length()) return ans; int[] pMap = new int[26]; for (int i = 0; i < p.length(); i++) { pMap[p.charAt(i) - 'a']++; } int[] sMap = new int[26]; int left = 0; for (int i = 0; i < s.length(); i++) { sMap[s.charAt(i) - 'a']++; if (i - left + 1 == p.length()) { if (Arrays.equals(sMap, pMap)) { ans.add(left); } sMap[s.charAt(left) - 'a']--; left++; } } return ans; }
5.至多包含两个不同字符的最长子串（159 - 中）
题目描述：给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度。
示例 :
示例 1: 输入: "eceba" 输出: 3 解释: t 是 "ece"，长度为3。 示例 2: 输入: "ccaabbb" 输出: 5 解释: t 是 "aabbb"，长度为5。
思路：维护一个窗口，元素类型至多两种。本题关键：如何判断窗口中的元素类型大于2了呢？
这里使用Hashmap记录当前字符在窗口中最靠右的索引值，为什么这么做呢？这样我们可以控制窗口的移动，right每右移一步：
- 若已经存在，更新map中当前元素最靠右的位置
- 若不存在，添加到map唯一存在，索引也是最靠右的
这样就好办了，如果我们元素类型超了2，即map的大小等于3。
- 记录最小索引值，用于下边删除和更新左边界。
- 删除操作是删除索引最小的那些或那个元素，因为记录的是右边界，这样我们也不用担心左边界问题。
代码实现：
public int lengthOfLongestSubstringTwoDistinct(String s) { int strLength = s.length(); if (strLength < 3) return strLength; int left = 0, right = 0; HashMap<Character, Integer> map = new HashMap<>(); int maxLen = 2; while (right < strLength) { map.put(s.charAt(right), right); right++; if (map.size() == 3) { int minIdx = Collections.min(map.values()); map.remove(s.charAt(minIdx)); left = minIdx + 1; } maxLen = Math.max(maxLen, right - left); } return maxLen; }
- ps：map.values()显示map中所有的值，返回值类型Collection<Integer>，用min()获取最小值。
- map.remove(key)：删除map中键为key的元素
6.至多包含k个不同字符的最长子串（340 - 难）
题目描述：给定一个字符串 s ，找出 至多 包含k个不同字符的最长子串 t ，并返回该子串的长度。
示例 :
示例 1: 输入: "eceba" 2 输出: 3 解释: t 是 "ece"，长度为3。 示例 2: 输入: "aa", 1 输出: 2 解释: t 是 "aa"，长度为2。
思路：维护一个窗口，元素类型至多k种。具体实现：类比上一题，解决方案还是使用hash表记录字符出现的最右索引。
代码实现：
public int lengthOfLongestSubstringKDistinct(String s, int k) { int strLength = s.length(); if (strLength < k + 1) return strLength; if (strLength * k == 0) return 0; int left = 0, right = 0; HashMap<Character, Integer> map = new HashMap<>(); int maxLen = k; while (right < strLength) { map.put(s.charAt(right), right); right++; if (map.size() == k + 1) { int minIdx = Collections.min(map.values()); map.remove(s.charAt(minIdx)); left = minIdx + 1; } maxLen = Math.max(maxLen, right - left); } return maxLen; }
7.替换后最长重复字符（424 - 中）
题目描述：给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。
在执行上述操作后，找到包含重复字母的最长子串的长度。
示例 :
输入：s = "ABAB", k = 2 输出：4 解释：用两个'A'替换为两个'B',反之亦然。
思路：可以想一下k = 0的情况（不替换字符），即求字符串的最长重复元素。关键点：如何判断一个字符串改变了k个字符就变成了一条连续的子串？
只要保证【当前子串的长度 <= 当前子串出现字符最多的个数 + k】，这样一定可以将当前子串替换为一条连续的子串（元素都相同）。
- 当满足上述条件，右边界扩张，并更新之前出现重复字母的最多个数（这个个数用一个数组记录）；
- 一旦不满足上述条件，我们移除左边界（直接在数组中将左边界对应的次数 - 1）；
注意：我们窗口维护了可能的最长子串，所以返回值为窗口大小，即s.length() - left。
代码实现：
public int characterReplacement(String s, int k) { int n = s.length(); if (s == null || n < 2 || n < k) return n; int[] map = new int[26]; int left = 0; int ans = 0, preMax = 0; for (int i = 0; i < n; i++) { int index = s.charAt(i) - 'A'; map[index]++; preMax = Math.max(preMax, map[index]); if (i - left + 1 > preMax + k) { map[s.charAt(left) - 'A']--; left++; } } return n - left; }
