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

无重复字符的最长子串

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

子字符串

子字符串 是字符串中连续的 非空 字符序列。

样例

---

Example

示例 1:
**输入: **s = “abcabcbb”
**输出: **3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。

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

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

提示：

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

思路

---

滑动窗口一：因为是子串，所以顺着让右指针逐渐+1。当遇到重复字符时，如bacda，为了不重复a，可以看出前一个a以及之前的都可以不要了，因此我们用一个hashset记录当前区间是否有某个字符，并不断左移直到右指针字符不再出现。
滑动窗口二：同上，但是我们可以简化左指针的移动过程，用一个last数组记录每个字符上一个的位置，令其直接跳跃到下一个字符。但是中间有的字符可能被跳过了，这些跳过的字符不在窗口里但是我们还没有更新，因此在更新左指针时需要检查这些是否还在窗口内，不在的就跳过表示过时了。

答案

---

Java

// 滑动窗口一
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        if (s.length() <= 1) {
            return s.length();
        }
        int l = 0, r = 0, ans = 1;
        while (r < s.length()) {
            char ch = s.charAt(r);
            while (set.contains(ch)) {
                set.remove(s.charAt(l));
                l++;
            }
            set.add(ch);
            ans = Math.max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
}
 
// 滑动窗口二
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) {
            return s.length();
        }
        int l = 0, r = 0, ans = 1;
        int[] last = new int[128];
        for (int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        while (r < s.length()) {
            int ch = s.charAt(r);
            int pre = last[ch];
            if (pre != -1 && l < pre + 1) {
                l = last + 1;
            }
            cnt[ch] = r;
            ans = Math.max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
}