【哈希表, 滑动窗口】无重复字符的最长子串

题目

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

剑指 Offer 48. 最长不含重复字符的子字符串

剑指 Offer II 016. 不含重复字符的最长子字符串

---

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 `"abc"，所以其`长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 `"b"`，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 `"wke"`，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，`"pwke"` 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

解题

方法一：哈希表 滑动窗口

思路

维护一个map集合(map)，键表示字符，值表示该字符上一次出现的索引（因为 s 的范围在ASCII码内，所以此处用一个长度256的数组代替）。

初始化所有字符上一次出现的索引为 -1 既可以表示还没在字符串中出现过。

维护两个指针(start, end)用来表示滑动窗口，两个指针都从 0 开始，遍历字符串：

• 取出 end 指针指向的字符 ch，把 ch 上次出现的索引 + 1 与 start 作比较，取较大的作当前滑动窗口的左边界。
• 用滑动窗口的长度更新 max，维护一个最长的滑动窗口长度。
• 把 ch 上次出现的索引更新为 end，end 自增。

最后返回 max 。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[] map = new int[256];
        Arrays.fill(map, -1);
        int max = 1;
        for (int start = 0, end = 0; end < n; end++) {
            char ch = s.charAt(right);
            start = Math.max(start, map[ch] + 1);
            max = Math.max(max, end - left + 1);
            map[ch] = end;
        }
        return max;
    }
}

优化

s 由英文字母、数字、符号和空格组成，所以 map 长度为 '~' - ' ' +1 就够用了。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[] map = new int[95];
        Arrays.fill(map, -1);
        int max = 1;
        for (int start = 0, end = 0; end < n; end++) {
            char ch = s.charAt(end);
            start = Math.max(start, map[ch - ' '] + 1);
            max = Math.max(max, end - start + 1);
            map[ch - ' '] = end;
        }
        return max;
    }
}

模板

【算法】工具 / 模板 - 滑动窗口 模板，更容易理解。

class Solution {
    static final int HASH_LEN = 128;

    public int lengthOfLongestSubstring(String s) {
        char[] chs = s.toCharArray();
        int n = chs.length;
        int[] window = new int[HASH_LEN];
        int left = 0, right = 0;
        int maxLen = 0;
        while (right < n) {
            char curr = chs[right++];
            if (++window[curr] < 2) {
                maxLen = Math.max(maxLen, right - left);
            } else {
                while (true) {
                    curr = chs[left++];
                    if (--window[curr] == 1) break;
                }
            }
        }
        return maxLen;
    }
}