Longest Substring Without Repeating Characters – Solution & Complexity

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

The optimal Longest Substring Without Repeating Characters solution runs in `O(n)` time and `O(min(n, k))` space. Sliding window with a last-seen index map to jump the left edge past repeats.

Q: What is the most efficient way to solve Longest Substring Without Repeating Characters?

Sliding window with a last-seen index map to jump the left edge past repeats. This gives `O(n)` time complexity, and is a classic strings, sliding window, and hashmap problem.

Q: How do you solve Longest Substring Without Repeating Characters in Python & JavaScript?

We provide a worked Longest Substring Without Repeating Characters solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Longest Substring Without Repeating Characters an easy or hard interview question?

Longest Substring Without Repeating Characters is generally rated **Medium**. It tests strings, sliding window, and hashmap, which are common coding-interview patterns.

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. 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. 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. 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. 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

Longest Substring Without Repeating Characters – Solution & Complexity

1. Understand the Goal

2. Brute Force Idea

3. Use a Sliding Window

4. Track Last Seen Positions

5. Final Solution and Complexity

FAQ

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

What is the most efficient way to solve Longest Substring Without Repeating Characters?

How do you solve Longest Substring Without Repeating Characters in Python & JavaScript?

Is Longest Substring Without Repeating Characters an easy or hard interview question?