{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Longest Substring Without Repeating Characters – Solution & Complexity

Interview solutions
/
Longest Substring Without Repeating Characters

Watch: Longest Substring Without Repeating Characters with a sliding window

Grow a window to the right one character at a time. When a character repeats, jump the left edge past its previous position, which a map of last-seen indices gives you in O(1). The answer is the widest window seen. O(n) time.

Solution Walkthrough

  1. Step 1: Understand the Goal

    • We need the length of the longest contiguous substring with no repeated characters.
    • A substring must keep characters in their original order and be continuous.
    • We only return the length, not the substring itself.

  2. Step 2: Brute Force Idea

    • Try every possible start index and extend until a duplicate appears.
    • Track the best length seen.
    • This works but can be O(n²) because many characters are scanned repeatedly.
    def length_of_longest_substring(s):
    best = 0
    for start in range(len(s)):
        seen = set()
        for end in range(start, len(s)):
            if s[end] in seen:
                break
            seen.add(s[end])
            best = max(best, end - start + 1)
    return best

  3. Step 3: Use a Sliding Window

    • Keep a window [left, right] that always contains unique characters.
    • Move right forward one character at a time.
    • If a character repeats, move left just past the previous occurrence.
    • This avoids rechecking characters that are already known to be valid.

  4. Step 4: Track Last Seen Positions

    • Store the most recent index for each character in a dictionary.
    • When s[right] was last seen inside the current window, update left.
    • Use max so left never moves backward.
    last_seen = {}
left = 0
best = 0

for right, char in enumerate(s):
    if char in last_seen and last_seen[char] >= left:
        left = last_seen[char] + 1
    last_seen[char] = right
    best = max(best, right - left + 1)

  5. Step 5: Final Solution and Complexity

    • Each character is processed once by the right pointer.
    • The left pointer only moves forward.
    • Time complexity is O(n).
    • Space complexity is O(k), where k is the number of distinct characters stored.
    def length_of_longest_substring(s: str) -> int:
    last_seen = {}
    left = 0
    best = 0

    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        best = max(best, right - left + 1)

    return best
Learn the Sliding Window pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Longest Substring Without Repeating Characters online (run code in the browser)Find All Anagrams in a String solution (medium)Minimum Window Substring solution (hard)First Unique Character in a String solution (easy)Group Anagrams solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?