题目描述

---

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度 。
力扣：3. 无重复字符的最长子串

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

题目分析

---

正如给出的这组样例输入，题目要求的 子串是连续的，而不是 离散的子序列
像这种连续的区间 ，定长和不定长的一些问题，都可采用滑动窗口来实现 ；
下面通过 abcabcbb 作为例子，描述滑动窗口的更新过程
以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb；
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
以 ab(c )abcbb 开始的最长字符串为 ab(cab)cbb；
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb；
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb；
以 abcab(c )bb 开始的最长字符串为 abcab(cb)b；
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b；
以 abcabcb(b) 开始的最长字符串为 abcabcb(b)；
一句话就能介绍其规则 ：维护一个 Set 集合，每当待添加的字符已经在集合内，这是需要将窗口中第一个字符从 Set 集合中移除即可。

AC代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 滑动窗口
        Set<Character> movie_window = new HashSet<>();
        char[] chars = s.toCharArray();
        int ans = 0;
        for(int i = 0 , rk = -1 ; i < chars.length ; i ++){
            // 移除窗口的第一个字符
            if(i != 0){
                movie_window.remove(chars[i - 1]);
            }
            // 托展窗口，添加窗口中没有重复的字符
            while(rk + 1 < chars.length && !movie_window.contains(chars[rk + 1])){
                movie_window.add(chars[rk + 1]);
                rk ++;
            }
            // 记录不重复字符的最大长度
            ans = Math.max(ans , movie_window.size());
        }
        return ans;
    }
}