Longest Substring Without Repeating Characters

Container With Most Water

Coin Change

Find the length of the longest substring without repeating characters.

Given a string `s`, find the length of the longest substring without repeating characters.

## Example
```
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
```

Constraints:
- `0 <= s.length <= 5 * 10^4`
- `s` consists of English letters, digits, symbols and spaces.

**Follow-up**
Can you return the substring itself, not just its length, without changing the overall time complexity?

- We need the length of the longest contiguous substring with no repeated characters.
- A substring must keep characters in their original order and be continuous.
- We only return the length, not the substring itself.

Understand the Goal

- Try every possible start index and extend until a duplicate appears.
- Track the best length seen.
- This works but can be O(n²) because many characters are scanned repeatedly.

Brute Force Idea

- Keep a window `[left, right]` that always contains unique characters.
- Move `right` forward one character at a time.
- If a character repeats, move `left` just past the previous occurrence.
- This avoids rechecking characters that are already known to be valid.

Use a Sliding Window

- Store the most recent index for each character in a dictionary.
- When `s[right]` was last seen inside the current window, update `left`.
- Use `max` so `left` never moves backward.

Track Last Seen Positions

- Each character is processed once by the right pointer.
- The left pointer only moves forward.
- Time complexity is O(n).
- Space complexity is O(k), where `k` is the number of distinct characters stored.