无重复字符的最长子串

无重复字符的最长子串

题目描述

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

示例

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

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

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

解析

双指针 + 滑动窗口：

• 通过维护一个双指针维护一个窗口，利用哈希表判断当前字符是否重复出现
• 不重复则移动右指针扩大窗口大小，重复出现则将左指针一直移动到当前字符只存在一个，更新最大值
• 最后通过左右指针的最大距离判断最长子串

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0, res = 0;
        while (right < s.length()) {
            char ch = s.charAt(right++);
            window.put(ch, window.getOrDefault(ch, 0) + 1);

            while (window.get(ch) > 1) {
                char ch2 = s.charAt(left++);
                window.put(ch2, window.get(ch2) - 1);
            }

            res = Math.max(res, right - left);
        }
        return res;
    }
}