最长无重复子串（Longest Substring Without Repeating Characters）

🟣最长无重复子串（Longest Substring Without Repeating Characters）

---

✅ 算法介绍

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

核心思路：
滑动窗口（Sliding Window）+ 哈希表（或数组）
窗口用两个指针 left 和 right 控制，哈希表记录字符上一次出现的位置，保证窗口内没有重复字符。

---

🟢 常见变体

变体	描述
LC3	最长无重复子串的长度
LC159	至多两个不同字符的最长子串
LC340	至多 K 个不同字符的最长子串
LC76	最小覆盖子串（最小滑动窗口）
LC567	字符串的排列

---

🔥 出现频率

⭐⭐⭐⭐

---

⏱️ 时间 & 空间复杂度

类别	复杂度
时间复杂度	O(n)
空间复杂度	O(n)

---

🐍 Python 实现

def length_of_longest_substring(s: str) -> int:
    left = 0
    max_len = 0
    used = {}

    for right in range(len(s)):
        if s[right] in used and used[s[right]] >= left:
            left = used[s[right]] + 1
        used[s[right]] = right
        max_len = max(max_len, right - left + 1)
    return max_len

---

☕ Java 实现

public int lengthOfLongestSubstring(String s) {
    int left = 0, maxLen = 0;
    Map<Character, Integer> map = new HashMap<>();
    for (int right = 0; right < s.length(); right++) {
        if (map.containsKey(s.charAt(right)) && map.get(s.charAt(right)) >= left) {
            left = map.get(s.charAt(right)) + 1;
        }
        map.put(s.charAt(right), right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

---

🐹 Go 实现

func lengthOfLongestSubstring(s string) int {
    left, maxLen := 0, 0
    used := make(map[byte]int)
    for right := 0; right < len(s); right++ {
        if idx, ok := used[s[right]]; ok && idx >= left {
            left = idx + 1
        }
        used[s[right]] = right
        if maxLen < right-left+1 {
            maxLen = right - left + 1
        }
    }
    return maxLen
}

---

🌐 JavaScript 实现

function lengthOfLongestSubstring(s) {
    let left = 0, maxLen = 0;
    const used = new Map();
    for (let right = 0; right < s.length; right++) {
        if (used.has(s[right]) && used.get(s[right]) >= left) {
            left = used.get(s[right]) + 1;
        }
        used.set(s[right], right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

---

🧵 C 实现

int lengthOfLongestSubstring(char * s){
    int used[128] = {0}, left = 0, maxLen = 0;
    for (int right = 0; s[right]; right++) {
        if (used[s[right]] > left) {
            left = used[s[right]];
        }
        used[s[right]] = right + 1;
        if (maxLen < right - left + 1) {
            maxLen = right - left + 1;
        }
    }
    return maxLen;
}

---

🧠 C++ 实现

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> used;
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.size(); right++) {
        if (used.count(s[right]) && used[s[right]] >= left) {
            left = used[s[right]] + 1;
        }
        used[s[right]] = right;
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

---

🌍 语言对照表（核心语句）

功能	Python	Java	Go	JavaScript	C	C++
滑动窗口	left, right	left, right	left, right	left, right	left, right	left, right
记录字符位置	dict	HashMap	map	Map	int[]	unordered_map
更新左指针	left = used[char] + 1	同左	同左	同左	同左	同左
最大长度更新	max()	Math.max()	if + manual	Math.max()	if + manual	max()

---

🧩 常见优化点

1. 若只涉及 ASCII 字符，可以用数组替代哈希表，提升常数性能。
2. 滑动窗口边界处理要小心，不要遗漏 left = used[char] + 1。
3. C 和 C++ 注意下标偏移，used[s[right]] = right + 1 是防止 0 初始值混淆。
4. 面试时如果能主动提到用数组优化空间，容易加分。

---

✨ 小技巧

• while 写法同样常见，但面试推荐用 for，因为更清晰。
• 拓展应用：该滑窗结构可直接套在「最长满足某条件的连续子串」类题目。
• left <= right 作为滑动窗口的标准边界写法。