// @Title: 无重复字符的最长子串 (Longest Substring Without Repeating Characters)
// @Author: qisiii
// @Date: 2021-07-11 23:43:22
// @Runtime: 757 ms
// @Memory: 38.5 MB
// @comment: 使用已经存在的indexOf方法
// @flag: BLUE
class Solution {
   public static int lengthOfLongestSubstring(String s) {
       char[] chars=s.toCharArray();
        List<Character> chuangkou=new ArrayList<>();
        int max=0;
        for (char aChar : chars) {
            if (chuangkou.contains(aChar)){
              chuangkou=chuangkou.subList(chuangkou.indexOf(aChar)+1,chuangkou.size());
            }
            chuangkou.add(aChar);
            max=max>chuangkou.size()?max:chuangkou.size();
        }
        return max;
}
}

// @Title: 无重复字符的最长子串 (Longest Substring Without Repeating Characters)
// @Author: qisiii
// @Date: 2022-03-10 20:36:20
// @Runtime: 893 ms
// @Memory: 41.6 MB
// @comment: 
// @flag: 
class Solution {
   public static int lengthOfLongestSubstring(String s) {
       char[] chars=s.toCharArray();
        List<Character> chuangkou=new ArrayList<>();
        int max=0;
        for (char aChar : chars) {
            if (chuangkou.contains(aChar)){
              chuangkou=chuangkou.subList(chuangkou.indexOf(aChar)+1,chuangkou.size());
            }
            chuangkou.add(aChar);
            max=max>chuangkou.size()?max:chuangkou.size();
        }
        return max;
}
}

// @Title: 无重复字符的最长子串 (Longest Substring Without Repeating Characters)
// @Author: qisiii
// @Date: 2024-04-10 22:19:49
// @Runtime: 75 ms
// @Memory: 44.5 MB
// @comment: hashMap滑动窗口方案
// @flag: WHITE
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> window = new HashMap<>();
        char[] chars = s.toCharArray();
        int left = 0, right = 0, max = 0;
        while (left < chars.length && right < chars.length) {
            // 不包含证明窗口中不存在重复字符
            if (!window.keySet().contains(chars[right])) {
                window.put(chars[right], right);
                right++;
            } else {
                // 重复则证明存在重复，需要冲重复的字符的下一个位置开始重新算作窗口
                max = Math.max(max, window.size());
                left = window.get(chars[right]) + 1;
                window.clear();
                window.put(chars[left], left);
                right = left + 1;
            }
        }
        return Math.max(max, window.size());
    }
}

// @Title: 无重复字符的最长子串 (Longest Substring Without Repeating Characters)
// @Author: qisiii
// @Date: 2024-04-10 23:38:06
// @Runtime: 6 ms
// @Memory: 43.7 MB
// @comment: 单次循环，通过每次移除一个来做处理，官方答案
// @flag: ORANGE
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> old=new HashSet<>();
        char[] chars=s.toCharArray();
        int max=0,right=0;
        for(int i=0;i<chars.length;i++){
            if(i!=0){
                old.remove(chars[i-1]);
            }
            while(right<chars.length&&!old.contains(chars[right])){
                old.add(chars[right]);
                right++;
            }
            max=Math.max(max,right-i);
        }
        return max;
    }
}

// @Title: 无重复字符的最长子串 (Longest Substring Without Repeating Characters)
// @Author: qisiii
// @Date: 2024-04-10 23:21:40
// @Runtime: 5 ms
// @Memory: 43.6 MB
// @comment: 单次循环，核心机制在与每次比较是否窗口之后，还要比较窗口的值是否比left大（即有可能是老值）这样子就避免了删除
// @flag: WHITE
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> window = new HashMap<>();
        char[] chars = s.toCharArray();
        int left = 0, right = 0, max = 0;
        while (left < chars.length && right < chars.length) {
            // 如果窗口包含，并且在窗口内
            if (window.keySet().contains(chars[right]) && window.get(chars[right]) >= left) {
                // 移动到重复的下一个位置
                left = window.get(chars[right]) + 1;
                // 更新重复字符的位置
                window.put(chars[right], right);
            } else {
                // 如果不存在往窗口里塞
                window.put(chars[right], right);
            }
            max = Math.max(max, right - left + 1);
            right++;
        }
        return max;
    }
}