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

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints

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

Thinking Process

  1. Sliding Window: Use two pointers (start and end) to maintain a valid window
  • Maintain a window [left, right] satisfying a constraint.
  • Expand right to grow; shrink left when invalid.
  • Fixed window: slide both pointers together.
Sliding window a b c d e window expand right, shrink left when invalid

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Fixed-size window (this problem) O(n) O(1) Window size known upfront
Variable-size window O(n) O(1) Expand/shrink until valid
Window + hash map O(n) O(k) Track character/count frequencies
Deque window max O(n) O(k) Monotonic deque for max/min in window

Solution

Time Complexity: O(n)
Space Complexity: O(min(m, n)) where m is the size of the charset

Use a sliding window approach with a hash map to track character positions and efficiently update the window boundaries.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int best = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (last.containsKey(ch)) {
                left = Math.max(left, last.get(ch) + 1);
            }
            last.put(ch, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}```

### Solution Explanation

**Approach:** Fixed-size window (this problem)

**Key idea:** 1. **Sliding Window**: Use two pointers (`start` and `end`) to maintain a valid window

**How the code works:**
1. **Sliding Window**: Use two pointers (`start` and `end`) to maintain a valid window
- Maintain a window `[left, right]` satisfying a constraint.
- Expand `right` to grow; shrink `left` when invalid.
- Fixed window: slide both pointers together.

**Walkthrough** — input `s = "abcabcbb"`, expected output `3`:

The answer is "abc", with the length of 3.

| Approach | Time Complexity | Space Complexity |
|----------|----------------|------------------|
| Brute Force | O(n³) | O(min(m, n)) |
| Sliding Window + Set | O(n) | O(min(m, n)) |
| Sliding Window + Hash Map | O(n) | O(min(m, n)) |
## Algorithm Breakdown

### 1. Initialize Variables
```cpp
int max_len = 0;
unordered_map<char, int> hashmap;

2. Expand Window

for (int start = 0, end = 0; end < s.length(); end++) {
    char cur = s[end];

3. Handle Duplicates

if (hashmap.find(cur) != hashmap.end() && hashmap[cur] >= start) {
    start = hashmap[cur] + 1;  // Move start past duplicate
}

4. Update and Track

hashmap[cur] = end;  // Update character position
max_len = max(max_len, end - start + 1);  // Update max length

Complexity

| Approach | Time Complexity | Space Complexity | |———-|—————-|——————| | Brute Force | O(n³) | O(min(m, n)) | | Sliding Window + Set | O(n) | O(min(m, n)) | | Sliding Window + Hash Map | O(n) | O(min(m, n)) |

Why This Solution is Optimal

  1. Single Pass: Each character is visited exactly once
  2. Efficient Lookup: Hash map provides O(1) character position lookup
  3. Smart Window Adjustment: Directly jumps to the correct position instead of sliding one by one
  4. Minimal Space: Only stores character positions, not the entire substring

Common Mistakes

  1. Empty string: s = "" → 0
  2. Single character: s = "a" → 1
  3. All same characters: s = "aaaa" → 1

  4. No duplicates: s = "abcdef" → 6

  5. Not checking if duplicate is within current window
  6. Using start = end instead of start = hashmap[cur] + 1
  7. Forgetting to update max_len after each iteration
  8. Not handling edge cases like empty string

References

Key Takeaways

  1. Sliding Window: Use two pointers (start and end) to maintain a valid window
  2. Hash Map Tracking: Store the last position of each character
  3. Efficient Updates: When a duplicate is found, move start to hashmap[cur] + 1
  4. Single Pass: Process each character exactly once