Longest Substring Without Repeating Characters

The problem

Given a string s, return the length of the longest substring in which no character appears twice. A substring is a run of characters that sit next to each other in s. The string can hold any ASCII characters, not only letters, and it can be empty, in which case the answer is 0.

What to write

function solve(s: string): number

Input
s = "abcabcbb"

Output
3

Input
s = "bbbbb"

Output
1

Constraints

0–10,000 ASCII characters.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The string can hold 10,000 characters, which makes about 50 million substrings, far too many to check one by one. Notice that a substring with a repeat in it stays broken however far you extend it to the right.

2. Hint 2: Ask a smaller question

   You are reading "abcabcbb" and have reached the second a. The three characters before it, "abc", have no repeat. What is the longest stretch without a repeat that ends at this a? Which characters did you have to give up?

3. Hint 3: Name the pattern

   You want the longest stretch of neighboring characters that obeys a rule. A stretch that breaks the rule can be repaired by cutting characters off its left end. Keep a window: its right edge takes in one character at a time, and its left edge moves up when a repeat comes in. This is a variable sliding window. Read the lesson on variable sliding window.

4. Hint 4: State the invariant

   After each step, the window from the left edge to the current character holds no character twice, and it is the longest such stretch that ends there. The left edge never moves backward.

5. Hint 5: Sketch the pseudocode

   left = 0, best = 0, and an empty map from character to latest position. For each position r with character c: if c is in the map, left = the larger of left and its stored position plus 1. Store r for c. best = the larger of best and r - left + 1. Return best.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Remember the latest index of each character. Move the left boundary past a repeat without ever moving it backward, then update the longest window.

The slow way

Look at every substring, check it for a repeated character, and keep the longest one that has none. It is correct, but a string of 10,000 characters has about 50 million substrings, and each check has to walk its substring again.

The insight

When a repeat comes in, you do not have to start over. Cut the stretch right after the earlier copy of the new character, and what is left has no repeat again. So the start of the stretch only ever moves forward, and every character is handled once.

Step by step

1. Start an empty window and note where each character was last seen. The window is the stretch from the left edge to the current character. Knowing where each character was last seen tells you in one step whether it repeats, and where the earlier copy is.
2. Move the left edge past this character's earlier copy, never backward. The earlier copy and everything before it have to go, so the edge lands one past that copy. A copy that is already left of the window changes nothing: taking the larger position keeps the edge in place.
3. Record this position as the character's latest. When this character shows up again, the copy that matters is the nearest one, and that is now this one. The older position is overwritten.
4. The window has no repeats now: keep the longest length seen. The window's length is the current position minus the left edge, plus one, because both ends are inside the window. That length replaces the best one only if it is larger.
5. The longest window seen is the answer. At every position the window was the longest stretch without a repeat ending there, and each one was measured. The longest substring ends at some position, so it was among them.

The same numbered steps are the comments in each solution.

function solve(s) {
  // 1. Start an empty window and note where each character was last seen
  let left = 0,
    best = 0;
  const seen = new Map();
  for (let r = 0; r < s.length; r++) {
    // 2. Move the left edge past this character's earlier copy, never backward
    if (seen.has(s[r])) left = Math.max(left, seen.get(s[r]) + 1);
    // 3. Record this position as the character's latest
    seen.set(s[r], r);
    // 4. The window has no repeats now: keep the longest length seen
    best = Math.max(best, r - left + 1);
  }
  // 5. The longest window seen is the answer
  return best;
}

function solve(s: string): number {
  // 1. Start an empty window and note where each character was last seen
  let left = 0,
    best = 0;
  const seen = new Map();
  for (let r = 0; r < s.length; r++) {
    // 2. Move the left edge past this character's earlier copy, never backward
    if (seen.has(s[r])) left = Math.max(left, seen.get(s[r]) + 1);
    // 3. Record this position as the character's latest
    seen.set(s[r], r);
    // 4. The window has no repeats now: keep the longest length seen
    best = Math.max(best, r - left + 1);
  }
  // 5. The longest window seen is the answer
  return best;
}

def solve(s):
    # 1. Start an empty window and note where each character was last seen
    left = best = 0
    seen = {}
    for right, char in enumerate(s):
        # 2. Move the left edge past this character's earlier copy, never backward
        if char in seen:
            left = max(left, seen[char] + 1)
        # 3. Record this position as the character's latest
        seen[char] = right
        # 4. The window has no repeats now: keep the longest length seen
        best = max(best, right - left + 1)
    # 5. The longest window seen is the answer
    return best

Example 1, traced

Input
s = "abcabcbb"

Output
3

Why it works

Each new character pushes the left edge past its own earlier copy, and the edge never moves back. So the window holds no character twice, and it cannot start any further left without bringing a second copy back in. That makes it the longest stretch without a repeat ending at each position, and the longest of those is kept.

Time and space

Time O(n) expected, extra space O(min(n, alphabet size)). Each of the n characters is visited once, with one map lookup and one update. In a hash map both take about one step on average, which is what "expected" means: O(n). The map holds one entry per different character, so it never outgrows the string or the alphabet.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Never let the left edge move backward. In "abba" the last a was seen at position 0, but the window already starts at position 2. Jumping back to position 1 brings both b's in: 3 instead of 2.
• Move the left edge one past the earlier copy, not onto it. Landing on the copy keeps both copies inside the window: "bbbbb" gives 2 instead of 1.
• Look the character up before you store its new position. Stored first, every character finds itself, the window is emptied each time and the answer is 0 for every string.

Pattern

Variable sliding window. Builds on Two Sum and Best Time to Buy And Sell Stock.

Keep going