Sushi Belt Without Repeats

Mediumsliding windowAlso known as Longest Substring Without Repeating Characters

At a conveyor-belt sushi bar, plates roll past in a fixed line. Each plate has a one-character code for its dish: s for salmon, t for tuna, e for eel and so on. The whole line for the evening is written as a string, like "stseat".

A food blogger wants to grab one unbroken run of plates as they pass, without ever taking the same dish twice. She wants to taste as many plates as possible this way. How long is the longest run of plates with no repeated code?

Your task

Write longestFreshRun(plates). Return the length of the longest stretch of consecutive characters in plates in which no character appears more than once.

Codes are case-sensitive: A and a are different dishes. An empty belt gives 0.

longestFreshRun(plates: string) → int

Examples

Example 1

Input

plates = "stseat"

Output

Why

The run seat (positions 2 to 5) has four different dishes. Any run of five plates contains a repeat: tseat has two t's, stsea has two s's.

Example 2

Input

plates = "tutor"

Output

Why

The best run is utor, length 4. If you restarted from scratch at every repeat you would miss it: on the second t you would start over at that t and lose the u before it.

Constraints

0 ≤ plates.length ≤ 10,000
plates contains letters (a-z, A-Z) and digits only.

Start with brute force

For every starting plate, extend the run to the right, keeping a set of dishes, until a repeat appears. Record the longest run found.

Here there are only 62 possible codes, so no run is longer than 62 and each start scans at most 63 plates: about 630,000 steps for 10,000 plates. That is fast enough, but only because the alphabet is small. The cost is O(n × k) for k possible codes, so with any Unicode character allowed it grows toward O(n²). And most of the work is repeated: when the run from start i hits a repeat, the run from i + 1 rescans almost the same plates.

Hints

0 of 4 shown

Hint 1
Take "tutor". You are holding the run tu and the next plate is t. Which plates do you have to give up to take it, and which can you keep?
Hint 2
When the new plate repeats a dish in your run, drop plates from the left of the run up to and including the earlier copy. Everything after that copy can stay.
Hint 3
So your run is a window with a left edge and a right edge. The right edge moves forward one plate at a time. The left edge only ever jumps forward, never back.
Hint 4
Keep a map from each code to the last position you saw it. For each plate at right: if its last position is inside the window (at or after left), set left to that position + 1. Then record the plate's position and update the best length with right - left + 1.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Keep a window plates[left..right] with no repeats. Each step, take one more plate on the right. If that plate's dish is already in the window, move left just past the earlier copy, and the window is valid again.

Trace "stseat":

right = 0, s. Window s, length 1.
right = 1, t. Window st, length 2.
right = 2, s. Last s was at 0, inside the window. left = 1. Window ts, length 2.
right = 3, e. Window tse, length 3.
right = 4, a. Window tsea, length 4.
right = 5, t. Last t was at 1, inside the window. left = 2. Window seat, length 4. Best = 4.

The check lastSeen ≥ left matters. In "abba", when the last a arrives, its earlier copy at position 0 is already outside the window (left is 2). Jumping left back to 1 would bring the repeated b back in.

Reference solution

function longestFreshRun(plates) {
  const lastSeen = new Map(); // code -> last position
  let left = 0, best = 0;
  for (let right = 0; right < plates.length; right++) {
    const c = plates[right];
    // Only an earlier copy inside the window forces left forward.
    if (lastSeen.has(c) && lastSeen.get(c) >= left) left = lastSeen.get(c) + 1;
    lastSeen.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

def longest_fresh_run(plates):
    last_seen = {}  # code -> last position
    left = best = 0
    for right, c in enumerate(plates):
        # Only an earlier copy inside the window forces left forward.
        if c in last_seen and last_seen[c] >= left:
            left = last_seen[c] + 1
        last_seen[c] = right
        best = max(best, right - left + 1)
    return best

TimeO(n)right visits each plate once, and left only moves forward.

SpaceO(k)k is the number of possible codes. The map holds at most one entry per code, so at most 62 here.

Learn the idea: Sliding Window Hash Tables Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code