【滑动窗口】无重复字符的最长子串

import java.util.HashSet;
import java.util.Set;

public class Solution {

    /**
     * 计算不含有重复字符的最长子串的长度
     * 使用滑动窗口算法
     *
     * @param s 输入字符串
     * @return 最长子串的长度
     */
    public int lengthOfLongestSubstring(String s) {
        // 1. 边界条件处理：如果字符串为空或长度为0，直接返回0
        if (s == null || s.length() == 0) {
            return 0;
        }

        // 2. 初始化数据结构
        // 使用 HashSet 来存储当前滑动窗口中的字符，用于快速判断字符是否重复
        Set<Character> charSet = new HashSet<>();
  
        // 定义滑动窗口的左边界指针，初始指向索引 0
        int left = 0;
  
        // 用于记录过程中出现的最大窗口长度
        int maxLength = 0;

        // 3. 开始滑动窗口
        // 右指针 right 负责向右探索新的字符，遍历整个字符串
        for (int right = 0; right < s.length(); right++) {
            // 获取当前右指针指向的字符
            char currentChar = s.charAt(right);

            // 4. 核心逻辑：判断重复
            // 如果当前字符 currentChar 已经存在于集合 charSet 中
            // 说明出现了重复字符，我们需要收缩窗口的左边界
            while (charSet.contains(currentChar)) {
                // 从集合中移除左指针指向的字符（即窗口最左边的字符）
                charSet.remove(s.charAt(left));
          
                // 左指针向右移动一位，缩小窗口
                // 这一步会一直执行，直到把那个造成重复的旧字符移出窗口为止
                left++;
            }

            // 5. 扩展窗口
            // 经过上面的 while 循环，当前窗口内一定不包含 currentChar
            // 所以可以安全地将当前字符加入集合
            charSet.add(currentChar);

            // 6. 更新最大长度
            // 当前窗口的长度计算公式为：右指针位置 - 左指针位置 + 1
            // 我们不断比较并保留历史最大值
            maxLength = Math.max(maxLength, right - left + 1);
        }

        // 7. 返回结果
        return maxLength;
    }

    // 主方法用于测试
    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例 1
        String s1 = "abcabcbb";
        // 预期输出: 3 (子串 "abc")
        System.out.println("输入: " + s1 + " -> 输出: " + solution.lengthOfLongestSubstring(s1));

        // 测试用例 2
        String s2 = "bbbbb";
        // 预期输出: 1 (子串 "b")
        System.out.println("输入: " + s2 + " -> 输出: " + solution.lengthOfLongestSubstring(s2));

        // 测试用例 3
        String s3 = "pwwkew";
        // 预期输出: 3 (子串 "wke")
        System.out.println("输入: " + s3 + " -> 输出: " + solution.lengthOfLongestSubstring(s3));
    }
}

int left = 0;
// 用于记录窗口状态，如字符频次、元素和等
Map/Array/Set windowState = ...; 
int result = ...; // 用于记录最终结果

for (int right = 0; right < array.length; right++) {
    // 1. 将 right 指向的元素加入窗口，并更新窗口状态
    // add array[right] to windowState
  
    // 2. 判断窗口状态是否不满足条件
    // 如果不满足，则移动 left 指针收缩窗口
    while (windowState 不满足条件) {
        // 将 left 指向的元素移出窗口，并更新窗口状态
        // remove array[left] from windowState
        left++;
    }
  
    // 3. 此时窗口状态满足条件，更新最终结果
    // result = max/min(result, right - left + 1);
}
return result;