1.無重復(fù)字符的最長(zhǎng)子串（3 - 中/劍指48）

題目描述：給定一個(gè)字符串蝗柔，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

示例 :

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"情龄，所以其長(zhǎng)度為 3迄汛。

思路：本題是面試的高頻題目捍壤，也是hash表的一個(gè)具體應(yīng)用。思路是維持一個(gè)隊(duì)列（窗口）鞍爱，保持隊(duì)列中的元素滿足題目要求（元素不重復(fù)）鹃觉。

具體實(shí)現(xiàn)是：使用hashmap記錄每個(gè)字符的索引位置，便于更新下一個(gè)窗口的左邊界睹逃，遍歷字符串盗扇。

• 如果窗口中含有這個(gè)元素，移動(dòng)移除左邊界元素（左邊索引+1）沉填；
• 否則加入窗口疗隶，更新最長(zhǎng)子串長(zhǎng)度。

代碼實(shí)現(xiàn)：

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.串聯(lián)所有單詞的子串（30 - 難）

題目描述：給定一個(gè)字符串 s 和一些長(zhǎng)度相同的單詞 words翼闹。找出 s 中恰好可以由 words 中所有單詞串聯(lián)形成的子串的起始位置斑鼻。

注意：子串要與 words 中的單詞完全匹配，中間不能有其他字符猎荠，但不需要考慮 words 中單詞串聯(lián)的順序卵沉。

示例 :

輸入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
輸出：[0,9]
解釋：
從索引 0 和 9 開始的子串分別是 "barfoo" 和 "foobar" 。
輸出的順序不重要, [9,0] 也是有效答案法牲。

思路：由于單詞長(zhǎng)度固定史汗，我們維護(hù)一個(gè)長(zhǎng)度為所有元素長(zhǎng)度總和的隊(duì)列（窗口）。本題也是考察hash表拒垃，鍵為存儲(chǔ)的單詞停撞，值存的單詞出現(xiàn)的次數(shù)。具體實(shí)現(xiàn)見代碼悼瓮。注意：

• 可以用indexOf()戈毒，判斷一個(gè)字符或者字符串是否存在一個(gè)字符串中，不存在返回負(fù)數(shù)横堡；否則將這個(gè)單詞加入哈希表埋市；

• 當(dāng)單詞數(shù)組長(zhǎng)度超過字符串長(zhǎng)度，直接剔除命贴。

• 對(duì)遍歷的每一個(gè)窗口道宅，用一個(gè)subMap記錄，left和right記錄左右邊界（更新的話胸蛛，是先將單詞從字符串中截取出來污茵，再在subMap中刪除）；

• 通過移動(dòng)右邊界right葬项，依次得到一個(gè)單詞泞当。如果wordMap中沒有這個(gè)單詞，更新左邊界民珍，清除這次記錄（包括subMap和單詞數(shù)量記錄數(shù)count）襟士；否則盗飒，加入subMap，注意count符合要求統(tǒng)計(jì)左邊界陋桂，超過限制刪除左邊界箩兽。

代碼實(shí)現(xiàn)：

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中沒有這個(gè)單詞，直接返回空
        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;
        // 統(tǒng)計(jì)每個(gè)符合要求的word
        Map<String, Integer> subMap = new HashMap<>();
        // 右窗口不能超出主串長(zhǎng)度
        while (right + oneLen <= s.length()) {
            // 得到一個(gè)單詞
            String word = s.substring(right, right + oneLen);
            right += oneLen;
            // words[]中沒有這個(gè)單詞章喉，那么當(dāng)前窗口肯定匹配失敗，直接右移到這個(gè)單詞后面
            if (!wordsMap.containsKey(word)) {
                left = right;
                subMap.clear();
                count = 0;
            } else {
                subMap.put(word, subMap.getOrDefault(word, 0) + 1);
                ++count;
                // 如果這個(gè)單詞出現(xiàn)的次數(shù)大于words[]中它對(duì)應(yīng)的次數(shù)身坐，又由于每次匹配和words長(zhǎng)度相等的子串
                // 如 ["foo","bar","foo","the"]  "| foobarfoobar| foothe"
                // 第二個(gè)bar雖然是words[]中的單詞秸脱，但是次數(shù)抄了，那么右移一個(gè)單詞長(zhǎng)度后 "|barfoobarfoo|the"
                // bar還是不符合部蛇，所以直接從這個(gè)不符合的bar之后開始匹配摊唇，也就是將這個(gè)不符合的bar和它之前的單詞(串)全移出去
                while (subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0)) {
                    // 從當(dāng)前窗口字符統(tǒng)計(jì)map中刪除從左窗口開始到數(shù)量超限的所有單詞(次數(shù)減一)
                    String w = s.substring(left, left + oneLen);
                    subMap.put(w, subMap.getOrDefault(w, 0) - 1);
                    // 符合的單詞數(shù)減一
                    --count;
                    // 左窗口位置右移
                    left += oneLen;
                }
                // 當(dāng)前窗口字符串滿足要求
                if (count == words.length) res.add(left);
            }
        }
    }
    return res;
}

3.最小覆蓋子串（76 - 難）

題目描述：給你一個(gè)字符串 s 、一個(gè)字符串 t 涯鲁。返回 s 中涵蓋 t 所有字符的最小子串巷查。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 抹腿。要求：時(shí)間復(fù)雜度O(N)岛请。

注意：如果 s 中存在這樣的子串，我們保證它是唯一的答案警绩，兩個(gè)字符串只含有英文字符崇败。

示例 :

輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"

思路：可以通過滑動(dòng)窗口解決，注意：最小覆蓋子串長(zhǎng)度不唯一肩祥，但至少與t相同后室。我們可以定義兩個(gè)變量：start（最小覆蓋子串的起始位置），size（最小覆蓋子串的長(zhǎng)度）

關(guān)鍵：如何判斷窗口中含有t的所有元素混狠？可以使用數(shù)組或者哈希表記錄字符出現(xiàn)的次數(shù)岸霹。

• 使用數(shù)組記錄t中（我們需要尋找的）字符的個(gè)數(shù)，cnt記錄要找字符總數(shù)将饺。

• 當(dāng)我們遍歷s字符串時(shí)贡避，遇到需要的字符我們就將他出現(xiàn)的次數(shù) - 1∮杌。總次數(shù)cnt == 0贸桶，此時(shí)找到一個(gè)覆蓋子串。

• 上述還不是一次尋找的最小覆蓋子串桌肴，需要找左邊界皇筛，如何找呢？還是通過出現(xiàn)的次數(shù)坠七，方法：在遍歷過程中水醋，s中出現(xiàn)每個(gè)的字符在need數(shù)組中-1旗笔，這樣我們?cè)谡易筮吔缡菫樨?fù)數(shù)，一定要恢復(fù)拄踪！

• 這時(shí)蝇恶，可以統(tǒng)計(jì)長(zhǎng)度size，更新起始索引start惶桐；

• 最終撮弧，移動(dòng)窗口，如何移動(dòng)（刪除左邊界元素）呢姚糊？將其加入need數(shù)組贿衍，更新左邊界和cnt個(gè)數(shù) + 1，下次遍歷出現(xiàn)這個(gè)字符就可以刪除（也可以理解為替換）救恨。

代碼實(shí)現(xiàn)：

public String minWindow(String s, String t) {
    if (s == null || s.length() == 0 || t == null || t.length() == 0 || s.length() < t.length()) {
        return "";
    }
    // 記錄需要字符的個(gè)數(shù)
    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)]--;
        // 窗口中已經(jīng)包含所有需要的字符
        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;
            }
            // 窗口移動(dòng)贸辈，注意更新need數(shù)組和cnt值
            need[s.charAt(left)]++;
            left++;
            cnt++;
        }
    }
    return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}

4.找到字符串中所有字母的異位詞（438 - 中）

題目描述：

給定一個(gè)字符串 s 和一個(gè)非空字符串 p，找到 s 中所有是 p 的字母異位詞的子串肠槽，返回這些子串的起始索引擎淤。字符串只包含小寫英文字母，并且字符串 s 和 p 的長(zhǎng)度都不超過 20100秸仙。

說明：

• 字母異位詞指字母相同嘴拢，但排列不同的字符串。
• 不考慮答案輸出的順序寂纪。

示例 :

輸入:
s: "cbaebabacd" p: "abc"

輸出:
[0, 6]

解釋:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母異位詞炊汤。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母異位詞。

思路：顯然滑窗弊攘，窗口大小為p字符串的長(zhǎng)度抢腐，關(guān)鍵：那么如何比較兩部分的元素是否是異位詞呢？

• 可以直接調(diào)庫函數(shù)Arrays.equals()襟交，判斷兩個(gè)字符串是否是異位詞（即兩個(gè)數(shù)組是否相同）迈倍。

• 本題仍使用數(shù)組存儲(chǔ)字符出現(xiàn)次數(shù)，但是本題兩個(gè)串申請(qǐng)了兩個(gè)空間捣域，方便進(jìn)行上邊的對(duì)比啼染。

• 這里判斷與上題相比簡(jiǎn)單了許多，只要長(zhǎng)度滿足我們就進(jìn)行判斷焕梅，兩部分異構(gòu)迹鹅，記錄起始索引；否則贞言，移除左邊界斜棚，這里直接在sMap刪除。

代碼實(shí)現(xiàn)：

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.至多包含兩個(gè)不同字符的最長(zhǎng)子串（159 - 中）

題目描述：給定一個(gè)字符串 s ，找出 至多 包含兩個(gè)不同字符的最長(zhǎng)子串 t 弟蚀，并返回該子串的長(zhǎng)度蚤霞。

示例 :

示例 1:
輸入: "eceba"
輸出: 3
解釋: t 是 "ece"，長(zhǎng)度為3义钉。

示例 2:
輸入: "ccaabbb"
輸出: 5
解釋: t 是 "aabbb"昧绣，長(zhǎng)度為5。

思路：維護(hù)一個(gè)窗口捶闸，元素類型至多兩種夜畴。本題關(guān)鍵：如何判斷窗口中的元素類型大于2了呢？

這里使用Hashmap記錄當(dāng)前字符在窗口中最靠右的索引值删壮，為什么這么做呢贪绘？這樣我們可以控制窗口的移動(dòng)，right每右移一步：

• 若已經(jīng)存在醉锅，更新map中當(dāng)前元素最靠右的位置

• 若不存在，添加到map唯一存在发绢，索引也是最靠右的

這樣就好辦了硬耍，如果我們?cè)仡愋统?，即map的大小等于3边酒。

• 記錄最小索引值经柴，用于下邊刪除和更新左邊界。

• 刪除操作是刪除索引最小的那些或那個(gè)元素墩朦，因?yàn)橛涗浀氖怯疫吔缗魅希@樣我們也不用擔(dān)心左邊界問題。

代碼實(shí)現(xiàn)：

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個(gè)不同字符的最長(zhǎng)子串（340 - 難）

題目描述：給定一個(gè)字符串 s 劳吠，找出 至多 包含k個(gè)不同字符的最長(zhǎng)子串 t 引润，并返回該子串的長(zhǎng)度。

示例 :

示例 1:
輸入: "eceba" 2
輸出: 3
解釋: t 是 "ece"痒玩，長(zhǎng)度為3淳附。

示例 2:
輸入: "aa", 1
輸出: 2
解釋: t 是 "aa"，長(zhǎng)度為2蠢古。

思路：維護(hù)一個(gè)窗口奴曙，元素類型至多k種。具體實(shí)現(xiàn)：類比上一題草讶，解決方案還是使用hash表記錄字符出現(xiàn)的最右索引洽糟。

代碼實(shí)現(xiàn)：

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.替換后最長(zhǎng)重復(fù)字符（424 - 中）

題目描述：給你一個(gè)僅由大寫英文字母組成的字符串，你可以將任意位置上的字符替換成另外的字符，總共可最多替換 k 次脊框。

在執(zhí)行上述操作后颁督，找到包含重復(fù)字母的最長(zhǎng)子串的長(zhǎng)度。

示例 :

輸入：s = "ABAB", k = 2
輸出：4
解釋：用兩個(gè)'A'替換為兩個(gè)'B',反之亦然浇雹。

思路：可以想一下k = 0的情況（不替換字符）沉御，即求字符串的最長(zhǎng)重復(fù)元素。關(guān)鍵點(diǎn)：如何判斷一個(gè)字符串改變了k個(gè)字符就變成了一條連續(xù)的子串昭灵？

只要保證【當(dāng)前子串的長(zhǎng)度 <= 當(dāng)前子串出現(xiàn)字符最多的個(gè)數(shù) + k】吠裆，這樣一定可以將當(dāng)前子串替換為一條連續(xù)的子串（元素都相同）。

• 當(dāng)滿足上述條件烂完，右邊界擴(kuò)張试疙，并更新之前出現(xiàn)重復(fù)字母的最多個(gè)數(shù)（這個(gè)個(gè)數(shù)用一個(gè)數(shù)組記錄）；

• 一旦不滿足上述條件抠蚣，我們移除左邊界（直接在數(shù)組中將左邊界對(duì)應(yīng)的次數(shù) - 1）祝旷；

注意：我們窗口維護(hù)了可能的最長(zhǎng)子串，所以返回值為窗口大小嘶窄，即s.length() - left怀跛。

代碼實(shí)現(xiàn)：

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;
}