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

题目 / Problem

中文： 给定一个字符串 s，找出其中不包含重复字符的最长子串，并返回该子串的长度。

子串必须是原字符串中连续的一段。
A substring must be a contiguous part of the original string.

English: Given a string s, find the length of the longest substring without duplicate characters.

示例 / Examples

Example 1

Input:  s = "abcabcbb"
Output: 3

解释 / Explanation:
一个最长无重复子串是 "abc"，长度为 3。
One longest substring without repeating characters is "abc", with length 3.

"bca" 和 "cab" 也是正确的最长子串。
"bca" and "cab" are also valid longest substrings.

Example 2

Input:  s = "bbbbb"
Output: 1

解释 / Explanation:
最长无重复子串是 "b"，长度为 1。
The longest substring without repeating characters is "b", with length 1.

Example 3

Input:  s = "pwwkew"
Output: 3

解释 / Explanation:
一个最长无重复子串是 "wke"，长度为 3。
One longest substring without repeating characters is "wke", with length 3.

"pwke" 虽然没有重复字符，但它不是连续子串，而是子序列，因此不能作为答案。
Although "pwke" has no repeated characters, it is a subsequence rather than a contiguous substring, so it is not a valid answer.

约束 / Constraints

0 <= s.length <= 10⁵
s 由英文字母、数字、符号和空格组成。
s consists of English letters, digits, symbols, and spaces.

解题思路：滑动窗口 / Approach: Sliding Window

使用区间 [left, right] 表示当前不包含重复字符的窗口：
Use [left, right] to represent the current window containing no duplicate characters:

right 从左到右遍历字符串，将新字符加入窗口。
right scans the string from left to right and adds each new character to the window.
left 表示当前窗口的左边界。
left marks the window's left boundary.
lastSeen 记录每个字符最近一次出现的下标。
lastSeen stores the most recent index of every character.

当字符 s[right] 之前出现过，并且它上次出现的位置仍在当前窗口内时，需要将 left 移动到该位置的后一位：
If s[right] appeared before and its previous position is still inside the current window, move left just past that position:

left = max(left, lastSeen.get(s[right]) + 1)

然后更新字符的最新位置，并使用窗口长度更新答案：
Then update the character's latest position and the maximum window length:

windowLength = right - left + 1

left 只会向右移动，不会回退，因此整个字符串只需遍历一次。
left only moves right and never backward, so the string needs only one traversal.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
  const lastSeen = new Map();
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    if (lastSeen.has(char)) {
      left = Math.max(left, lastSeen.get(char) + 1);
    }

    lastSeen.set(char, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

执行过程 / Walkthrough

以 s = "abcabcbb" 为例：
For s = "abcabcbb":

`right`	字符 / Character	上次位置 / Last Seen	新的 `left`	当前窗口 / Window	`maxLength`
0	`a`	—	0	`"a"`	1
1	`b`	—	0	`"ab"`	2
2	`c`	—	0	`"abc"`	3
3	`a`	0	1	`"bca"`	3
4	`b`	1	2	`"cab"`	3
5	`c`	2	3	`"abc"`	3
6	`b`	4	5	`"cb"`	3
7	`b`	6	7	`"b"`	3

最终最长窗口长度为 3。
The final maximum window length is 3.

`"pwwkew"` 的关键变化 / Key Changes for `"pwwkew"`

p → pw → 遇到第二个 w，将 left 移到 2
w → wk → wke → 遇到最后一个 w，将 left 移到 3

p → pw → second w moves left to 2
w → wk → wke → final w moves left to 3

最长连续窗口是 "wke" 或 "kew"，长度为 3。
The longest contiguous window is "wke" or "kew", with length 3.

为什么需要 `Math.max()`？ / Why Is `Math.max()` Necessary?

字符上一次出现的位置可能已经位于当前窗口左侧。例如 s = "abba"：
A character's previous occurrence may already lie to the left of the current window. Consider s = "abba":

处理第二个 b 后，left 已经移动到下标 2。
After processing the second b, left moves to index 2.
处理最后一个 a 时，a 上次出现在下标 0。
When processing the final a, its previous occurrence is at index 0.
如果直接使用 left = 0 + 1，left 会错误地从 2 回退到 1。
Setting left = 0 + 1 directly would incorrectly move left backward from 2 to 1.

因此必须写成：
Therefore, use:

left = Math.max(left, lastSeen.get(char) + 1);

这样左边界永远不会向后移动。
This guarantees that the left boundary never moves backward.

复杂度 / Complexity

设字符串长度为 n。
Let the string length be n.

时间复杂度：O(n)，right 遍历字符串一次，left 只向右移动。
Time: O(n), because right scans the string once and left only moves right.
空间复杂度：O(k)，其中 k 是字符串中不同字符的数量；在本题有限字符集下可以视为 O(1)。
Space: O(k), where k is the number of distinct characters; with the problem's bounded character set, this can be treated as O(1).

使用 Set 的滑动窗口 / Sliding Window with a Set

也可以使用 Set 保存当前窗口中的字符。遇到重复字符时，从左侧逐个删除，直到重复字符被移出窗口：
A Set can instead store the characters in the current window. Upon finding a duplicate, remove characters from the left until the duplicate leaves the window:

function lengthOfLongestSubstringWithSet(s) {
  const window = new Set();
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    while (window.has(s[right])) {
      window.delete(s[left]);
      left++;
    }

    window.add(s[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

时间复杂度 / Time: O(n)，每个字符最多加入和移出集合各一次。
Every character is added to and removed from the set at most once.
空间复杂度 / Space: O(k)

Map 解法可以通过上次出现位置直接跳转左边界；Set 解法则逐个移除窗口左侧字符。
The Map solution jumps the left boundary directly using the previous index, while the Set solution removes left-side characters one by one.

子串与子序列 / Substring vs. Subsequence

子串必须连续，例如 "wke" 是 "pwwkew" 的子串。
A substring must be contiguous; "wke" is a substring of "pwwkew".
子序列可以跳过字符，例如 "pwke" 是子序列，但不是子串。
A subsequence may skip characters; "pwke" is a subsequence but not a substring.

本题只能使用连续子串。
Only contiguous substrings are valid in this problem.

易错点 / Common Pitfalls

返回的是最长子串的长度，不是子串本身。
Return the length of the longest substring, not the substring itself.
窗口必须保持连续，不能跳过中间字符拼接结果。
The window must remain contiguous; characters cannot be skipped and recombined.
更新 left 时必须使用 Math.max()，防止左边界回退。
Use Math.max() when updating left so the boundary never moves backward.
更新答案时，当前窗口长度是 right - left + 1。
The current window length is right - left + 1.
空字符串应返回 0。
Return 0 for an empty string.
空格和符号也是普通字符，同样需要参与重复判断。
Spaces and symbols are ordinary characters and must also be checked for duplication.

Longest Substring Without Repeating Characters