🔗 无重复字符的最长子串

题目来源：3. 无重复字符的最长子串 – 力扣（LeetCode）

---

📌 题目描述

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

注意：子串（substring）是原字符串中连续的一段字符序列，不同于子序列（subsequence）。

---

✅ 示例解析

示例 1：

• 输入：s = "abcabcbb"
• 输出：3
• 解释：无重复字符的最长子串是 "abc"，长度为 3。

示例 2：

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

示例 3：

• 输入：s = "pwwkew"
• 输出：3
• 解释：最长子串是 "wke"，长度为 3。
  注意："pwke" 是一个子序列，不是子串，因此不满足条件。

示例 4：

• 输入：s = ""
• 输出：0
• 解释：空字符串，长度为 0。

---

⚠️ 提示

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

---

💡 解法：滑动窗口 + 哈希表（一次遍历）—— O(n) 时间

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>(); 
        int index = 0; 
        int ans = 0;  
        char[] sArr = s.toCharArray();
        for (int i = 0; i < sArr.length; i++) {
            if (map.containsKey(sArr[i])) {
                index = Math.max(index, map.get(sArr[i]) + 1);
            }
            ans = Math.max(ans, i - index + 1);
            map.put(sArr[i], i);
        }

        return ans;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  字符串只遍历一次，哈希表的 put 和 get 操作均为 O(1)，整体为线性时间。
• 空间复杂度：O(min(m, n))
  • m 是字符集大小（如 ASCII 为 128，Unicode 更大）
  • n 是字符串长度
    哈希表最多存储不同字符的数量，因此空间为字符集与字符串长度的较小值。

---

🧩 解题思路

1. 滑动窗口思想：
   • 使用两个指针维护一个不含重复字符的窗口 [index, i]。
   • i 是右指针，不断向右扩展。
   • index 是左指针，表示当前无重复子串的起始位置。
2. 哈希表记录字符位置：
   • 用 Map<Character, Integer> 记录每个字符最后一次出现的索引。
   • 当遇到重复字符时，将左边界 index 移动到该字符上次出现位置的后一位，确保窗口内无重复。
3. 关键点：左边界不回退
   • 使用 index = Math.max(index, map.get(sArr[i]) + 1) 而不是直接赋值。
   • 防止左边界“倒退”，例如 "abba"：当遇到第二个 'a' 时，左边界应在 'b' 之后，不能回到第一个 'a' 后面。
4. 更新最大长度：
   • 每次右指针移动后，计算当前窗口长度 i - index + 1，并更新 ans。
5. 举例说明：
   对于 "abba"：
   • i=0: 'a' → map={a:0}, ans=1
   • i=1: 'b' → map={a:0,b:1}, ans=2
   • i=2: 'b' 重复 → index = max(0, 1+1)=2, ans=max(2, 2-2+1)=2
   • i=3: 'a' 重复 → index = max(2, 0+1)=2, ans=max(2, 3-2+1)=2
     最终结果为 2，对应子串 "ab" 或 "ba"。