无重复字符的最长子串「变题」

3. 无重复字符的最长子串

开头先来一个小插曲，关于「滑动窗口」相关的总结可见 滑动窗口

这是一个滑动窗口的入门题，先直接给出代码：

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> win = new HashMap<>();
    int l = 0, r = 0, ans = 0;
    while (r < s.length()) {
        char c = s.charAt(r++);
        win.put(c, win.getOrDefault(c, 0) + 1);
        while (win.get(c) > 1) {
            char d = s.charAt(l++);
            win.put(d, win.get(d) - 1);
        }
        ans = Math.max(ans, r - l);
    }
    return ans;
}

这么简单，还总结干嘛！！因为看到很多人说这个题目考了很多「变题」

变题一：允许一个字符重复一次

xxxxxxxxxx
// 方法一
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> win = new HashMap<>();
    // 记录重复一次的字符
    Map<Character, Integer> repeat = new HashMap<>();
    int l = 0, r = 0, ans = 0;
    while (r < s.length()) {
        char c = s.charAt(r++);
        win.put(c, win.getOrDefault(c, 0) + 1);
        // 字符重复了一次
        if (win.get(c) > 1) repeat.put(c, win.get(c));
        // 收缩窗口
        while (repeat.size() > 1 || repeat.getOrDefault(c, 0) > 2) {
            char d = s.charAt(l++);
            win.put(d, win.get(d) - 1);
            if (repeat.containsKey(d)) {
                repeat.put(d, repeat.get(d) - 1);
                // 只出现了一次或零次，移除
                if (repeat.get(d) < 2) repeat.remove(d);
            }
        }
        ans = Math.max(ans, r - l);
    }
    return ans;
}
// 方法二
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> win = new HashMap<>();
    int l = 0, r = 0, repeat = 0;
    int ans = 0;
    while (r < s.length()) {
        char c = s.charAt(r++);
        win.put(c, win.getOrDefault(c, 0) + 1);
        if (win.get(c) > 1) repeat++;
        while (repeat > 1) {
            char d = s.charAt(l++);
            if (win.get(d) > 1) repeat--;
            win.put(d, win.get(d) - 1);
        }
        ans = Math.max(ans, r - l);
    } 
    return ans;
}

变题二：允许所有字符重复一次

xxxxxxxxxx
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> win = new HashMap<>();
    int l = 0, r = 0, ans = 0;
    while (r < s.length()) {
        char c = s.charAt(r++);
        win.put(c, win.getOrDefault(c, 0) + 1);
        // 改为大于 2 即可
        while (win.get(c) > 2) {
            char d = s.charAt(l++);
            win.put(d, win.get(d) - 1);
        }
        ans = Math.max(ans, r - l);
    }
    return ans;
}

变题三：最多有两个不同字符的最长子串

可见题目 最多有两个不同字符的最长子串

xxxxxxxxxx
public int lengthOfLongestSubstringTwoDistinct(String s) {
    // Write your code here
    Map<Character, Integer> win = new HashMap<>();
    int l = 0, r = 0, ans = 0;
    while (r < s.length()) {
        char c = s.charAt(r++);
        win.put(c, win.getOrDefault(c, 0) + 1);
        // 窗口内字符多于 2 个
        while (win.size() > 2) {
            char d = s.charAt(l++);
            win.put(d, win.get(d) - 1);
            if (win.get(d) == 0) win.remove(d);
        }
        ans = Math.max(ans, r - l);
    }
    return ans;
}

变题四：至少有 K 个重复字符的最长子串

可见题目 至少有 K 个重复字符的最长子串

方法一：由于s仅由小写英文字母组成，所以限制窗口内不同字符的数量，从 1 到 26，便可以枚举所有可行子串

xxxxxxxxxx
public int longestSubstring(String s, int k) {
    int ans = 0;
    for (int i = 1; i <= 26; i++) {
        Map<Character, Integer> win = new HashMap<>();
        Set<Character> repeat = new HashSet<>();
        int l = 0, r = 0;
        while (r < s.length()) {
            char c = s.charAt(r++);
            win.put(c, win.getOrDefault(c, 0) + 1);
            if (win.get(c) == k) repeat.add(c);
            while (win.size() > i) {
                char d = s.charAt(l++);
                if (win.get(d) == k) repeat.remove(d);
                win.put(d, win.get(d) - 1);
                if (win.get(d) == 0) win.remove(d);
            }
            if (win.size() == repeat.size()) ans = Math.max(ans, r - l);
        }
    }
    return ans;
}

方法二：分治！先对每一个字符计数，以个数< k的字符为分割点

xxxxxxxxxx
public int longestSubstring(String s, int k) {
    if (s.length() < k) return 0;
    int[] cnt = new int[26];
    for (char c : s.toCharArray()) cnt[c - 'a']++;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] != 0 && cnt[i] < k) {
            int res = 0;
            for (String sub : s.split(String.valueOf((char) (i + 'a')))) {
                res = Math.max(res, longestSubstring(sub, k));
            }
            return res;
        }
    }
    return s.length();
}