Longest Unique-Character Window

Interview Problem Intermediate Medium Sliding Window Hash Map String

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.lengthOfLongestSubstring(text). Return the maximum length of a contiguous substring containing no repeated character. The empty string returns 0.

Starter code

class Solution:
    def lengthOfLongestSubstring(self, text: str) -> int:
        pass

Test cases

repeated-blocks

{
  "args": [
    "abcabcbb"
  ]
}

Expected: 3

Wizard outline

Step 1: Initialize Solution.lengthOfLongestSubstring
Replace the empty starter with the first real state owned by Solution.lengthOfLongestSubstring. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Repeated Blocks case
Complete the readable core algorithm for one representative Interview case. Maintain a valid variable-size window and jump its left boundary past the latest conflicting index.
Step 4: Harden the Boundary Must Not Rewind boundary
Repair the reviewed boundary and pass the complete submission contract. Before measuring each window, left is greater than every previous occurrence of the current character within that window, so all window characters are unique; taking the maximum considers every valid right endpoint.

Footguns and prerequisites

Never move the left boundary backward when the repeated character lies outside the current window.
arrays strings two pointers sliding window
hashing and sets

Reviewed references

Practice prerequisites

Shrink Until the Window Is Valid(opens in a new tab)
Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing longest substring without repeating as a complete Interview Problem.

Recommended approach and implementation

Store each character's latest index and move left to at least one position after a duplicate inside the current window.

Why it works: Before measuring each window, left is greater than every previous occurrence of the current character within that window, so all window characters are unique; taking the maximum considers every valid right endpoint.

class Solution:
    def lengthOfLongestSubstring(self, text):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        latest = {}
        left = 0
        best = 0
        for right, character in enumerate(text):
            if character in latest:
                left = max(left, latest[character] + 1)
            latest[character] = right
            best = max(best, right - left + 1)
        return best