Coding interview problems › Sliding Window

🪟 Sliding Window Medium

Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters explained: a sliding window with a last-seen map jumps the left edge past repeats in O(n). Tested Python.

Also searched as: longest substring without repeating characters sliding window · longest unique substring

🪟

Try it live Free

Sliding Window

Watch a window slide across the array, adding what enters and dropping what leaves. Here the window's size is not fixed: it grows on the right and the left edge jumps forward whenever a repeat enters.

Also useful: Hash Tables

Open the playground →

The problem

Given a string s, return the length of the longest contiguous substring in which no character appears more than once.

Inputs = "abcabcbb"
Output3

"abc".

Inputs = "pwwkew"
Output3

"wke"; "pwke" is a subsequence, not a substring.

The key insight

Keep a window [left, right] that never contains a repeat. Grow it one character at a time on the right. When the new character already appears inside the window, jump left to just past its previous position. A map of each character's last index makes that jump O(1).

Brute force first: Checking every substring for uniqueness is O(n²) or worse.

Step-by-step approach

  1. Keep last, a map from character to its most recent index, and left = 0.
  2. For each right and character ch: if ch was seen at an index >= left, set left = last[ch] + 1.
  3. Record last[ch] = right.
  4. Update the best length with right - left + 1.
  5. Return the best length.

Python solution

PYTHON 3tested
def length_of_longest_substring(s):
    last = {}                      # char -> last index seen
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1    # jump past the previous copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Complexity

TimeO(n)
SpaceO(k)

Both window edges only move forward, so each character is handled once. The map holds at most k distinct characters.

Common mistakes

Frequently asked questions

What is the time and space complexity of Longest Substring Without Repeating Characters?

The sliding window solution is O(n) time and O(k) space, where k is the number of distinct characters (at most the alphabet size).

Why not move left one step at a time?

That also works in O(n) if you remove characters from a set as left moves. Jumping directly with a last-index map just skips those steps.

How do I return the substring itself?

Remember the left and right indices whenever best improves, then slice s at the end.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Sliding Window Sliding Window lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.