# Longest Substring Without Repeating Characters

# Problem

Find the length of the longest substring without repeating characters. A **substring** is a continuous part of a string; characters cannot be skipped.

[View the problem on LeetCode](https://leetcode.com/problems/longest-substring-without-repeating-characters/description/).

### Examples

| Input | Answer | One longest substring |
| --- | --- | --- |
| `"abcabcbb"` | 3 | `"abc"` |
| `"bbbbb"` | 1 | `"b"` |
| `"pwwkew"` | 3 | `"wke"` |
| `""` | 0 | Empty string |

In `"pwwkew"`, `"pwke"` is not a substring because it skips a character.

### Constraints

- `0 <= s.length() <= 10^5`
- The string contains English letters, digits, symbols, and spaces.

# Solution

## Approach - Sliding window with last-seen indices

This follows [Pattern 2: longest valid window](https://chetan77.hashnode.dev/2-pointers-sliding-window-templates).

Keep a window from `l` to `r` and a map storing each character's latest index.

For each character at `r`:

1. Look up its previous index.
2. If that index is inside the window (`prevIndex >= l`), move `l` to `prevIndex + 1`, just past the duplicate.
3. Store the current index and update the maximum using `r - l + 1`.

**After moving** `l`**, the window has no duplicates.** Jumping just past the previous occurrence removes the duplicate while keeping the longest valid window ending at `r`.

### Why must we check `prevIndex >= l`?

A character's previous occurrence may already be outside the window. **Never move** `l` **backward.**

For `s = "abba"` (indices start at 0):

| r | Character | Action | Valid window | Best length |
| --- | --- | --- | --- | --- |
| 0 | `a` | First occurrence | `"a"` | 1 |
| 1 | `b` | First occurrence | `"ab"` | 2 |
| 2 | `b` | Previous index 1 is inside; move `l` to 2 | `"b"` | 2 |
| 3 | `a` | Previous index 0 is outside; keep `l = 2` | `"ba"` | 2 |

At the final `a`, moving `l` backward to 1 would create `"bba"`, which contains a duplicate.

## Java solution

### My solution

```java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0;
        int r = 0;
        int n = s.length();
        int maxLength = 0;

        Map<Character, Integer> lastSeen = new HashMap<>();

        for (r = 0; r < n; r++) {
            char chr = s.charAt(r);

            if (lastSeen.containsKey(chr)) {
                int prevIndex = lastSeen.get(chr);
                if (l <= prevIndex) {
                    l = prevIndex;
                    l += 1;
                }
            }

            lastSeen.put(chr, r);
            maxLength = Math.max(maxLength, r - l + 1);
        }

        return maxLength;
    }
}
```

### Cleaner version

The same logic, with one map lookup and a single assignment to move `l`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0;
        int maxLength = 0;
        Map<Character, Integer> lastSeen = new HashMap<>();

        for (int r = 0; r < s.length(); r++) {
            char chr = s.charAt(r);
            Integer prevIndex = lastSeen.get(chr);

            // Skip the duplicate only if it is inside the window.
            if (prevIndex != null && prevIndex >= l) {
                l = prevIndex + 1;
            }

            lastSeen.put(chr, r);
            maxLength = Math.max(maxLength, r - l + 1);
        }

        return maxLength;
    }
}
```

## Complexity

- **Time: O(n) expected** — visit each character once, with expected O(1) map operations.
- **Extra space: O(min(n, A))** — one entry per distinct character, where `A` is the character-set size.