1 问题

给定一个字符串 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 由英文字母、数字、符号和空格组成

2 解题思路

2.1 双指针

思路：

利用map存储字符及其索引下标，双指针记录子串的头尾，当右指针right移动过程中，

若s[right]不存在于map中，则更新子串长度，记录该字符；
否则，s[right]为重复字符，若左指针left>map中记录的s[right]下标+1，则更新左指针，同样更新子串长度，更新map中该重复字符下标。

以字符串pwwkew为例：

1)初始化
初始化
2)map中不包含p，记录该字符至map中，同时，更新子串长度，此时为1
处理字符p
3)同理，记录w，更新子串长度为2
处理字符w
4)map中已包含w了，则更新左指针start=max(start, map[‘w’])，并更新w在map中的下标，此时子串最大长度仍为2
处理重复字符w
5)map中不包含字符k，同第2)步
处理字符k
6)map中不包含字符e，同第2)步
处理字符e
7)map中包含w，同第4)步
处理重复字符w

2.2 滑动窗口

公式，参见【LeetCode】643.子数组最大平均数I.

思路：

双指针，右指针移动过程中，若字符不存在于记录集合set中，则扩大窗口，并更新子串长度；
若遇见重复字符，缩小窗口，即移除最左指针所指字符，直到set中不包含右指针所指字符为止；
重复上述过程，直至遍历字符串完毕，返回子串最大长度。

3 代码

class Solution {
    /**
     * 双指针解法
     * @param s 字符串
     * @return 长度
     */
    public int lengthOfLongestSubstring(String s) {
        if (null == s || s.length() == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int left = 0;
        int right = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (right < s.length()) {
            //如果map包含字符，则若left>map.get(s.charAt(right)) + 1，更新左指针，相当于将左指针指向出现相同字符的索引值+1的位置
            if (map.containsKey(s.charAt(right))) {
                left = Math.max(map.get(s.charAt(right)) + 1, left);
            }
            //计算长度
            max = Math.max(max, right - left + 1);
            //记录字符索引
            map.put(s.charAt(right), right++);
        }
        return max;
    }

    /**
     * 滑动窗口解法
     * @param s 字符串
     * @return 长度
     */
    public int lengthOfLongestSubstring2(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}