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

输入：s = "abcabcbb"
输出：3
解释：最长不重复子串是 "abc"，长度为 3

输入：s = "bbbbb"
输出：1
解释：最长不重复子串是 "b"，长度为 1

输入：s = "pwwkew"
输出：3
解释：最长不重复子串是 "wke"，长度为 3

s = "abcabcbb"

"a"     -> 不重复，长度 1
"ab"    -> 不重复，长度 2
"abc"   -> 不重复，长度 3
"abca"  -> 有重复 a，停止
"b"     -> 不重复，长度 1
"bc"    -> 不重复，长度 2
"bca"   -> 不重复，长度 3
"bcab"  -> 有重复 b，停止
...

s = "abcabcbb"

初始：left = 0, right = 0, window = {}

right = 0, 进入 a：window = {a:1}，合法，ans = 1
right = 1, 进入 b：window = {a:1, b:1}，合法，ans = 2
right = 2, 进入 c：window = {a:1, b:1, c:1}，合法，ans = 3
right = 3, 进入 a：window = {a:2, b:1, c:1}，重复！
  left = 0, 移出 a：window = {a:1, b:1, c:1}，不再重复，left = 1
right = 4, 进入 b：window = {a:1, b:2, c:1}，重复！
  left = 1, 移出 b：window = {a:1, b:1, c:1}，不再重复，left = 2
...

left = 0
window = {}  # 或其他数据结构，维护窗口状态

for right in range(len(s)):
    # 1. 将 s[right] 加入窗口
    window[s[right]] = window.get(s[right], 0) + 1

    # 2. 若窗口状态不合法，从左边收缩
    while window_is_invalid():
        window[s[left]] -= 1
        left += 1

    # 3. 此时窗口合法，更新答案
    ans = max(ans, right - left + 1)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        n = len(s)
        for i in range(n):
            seen = set()
            for j in range(i, n):
                if s[j] in seen:
                    break
                seen.add(s[j])
                ans = max(ans, j - i + 1)
        return ans

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let bytes = s.as_bytes();
        let n = bytes.len();
        let mut ans = 0;

        for i in 0..n {
            let mut seen = std::collections::HashSet::new();
            for j in i..n {
                if !seen.insert(bytes[j]) {
                    break;
                }
                ans = ans.max(j - i + 1);
            }
        }

        ans as i32
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        count = {}
        left = 0
        ans = 0

        for right, ch in enumerate(s):
            count[ch] = count.get(ch, 0) + 1

            while count[ch] > 1:
                left_ch = s[left]
                count[left_ch] -= 1
                left += 1

            ans = max(ans, right - left + 1)

        return ans

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let bytes = s.as_bytes();
        let mut count = [0u32; 128];
        let mut left = 0;
        let mut ans = 0;

        for right in 0..bytes.len() {
            let ch = bytes[right] as usize;
            count[ch] += 1;

            while count[ch] > 1 {
                count[bytes[left] as usize] -= 1;
                left += 1;
            }

            ans = ans.max(right - left + 1);
        }

        ans as i32
    }
}