Longest Substring Without Repeating Characters

This is the question that teaches you the sliding window. So many people try to brute force it first. Then they hit a wall on speed. The interviewer wants to see if you can slide a window across the string instead of checking every piece by hand. Get this one and a whole family of problems opens up.

🎯 The Problem

You get a string. Here are the rules.

• Find the length of the longest part that has no repeated character.
• A part that sits next to itself is a substring. A substring is a run of characters with nothing skipped in between.
• The substring must have all different characters.
• Return only the length, not the substring itself.

Take the string "abcabcbb". The longest run with all different letters is "abc", length 3. After that you hit another a, so the run breaks.

Input:  s = "abcabcbb"
Output: 3

Explanation: The longest substring with all unique characters is "abc", which has length 3.

Here is the string with the best window drawn over it. The window is the part we are looking at right now.

🐢 Approach 1: Check Every Substring (Brute Force)

The idea in one line: build every substring and check each one for a repeat.

The idea:

• Start at each position in the string.
• Stretch out one character at a time from there.
• Each stretch, look back to see if the new character already showed up.

How it works:

• If the new character is a repeat, stop that run.
• Keep the longest run with no repeat.

Why it is weak:

• You build and check every substring.
• That repeats a lot of work.
• The nested passes make it O(n²) or worse.

Here is the brute-force code for that idea:

def length_of_longest_substring(s):
    best = 0
    for left in range(len(s)):
        seen = set()
        for right in range(left, len(s)):
            if s[right] in seen:
                break
            seen.add(s[right])
            best = max(best, right - left + 1)
    return best

⚡ Approach 2: Sliding Window With a Set (Best)

The idea in one line: keep a window of unique characters in a set, growing on the right and shrinking on the left.

The idea:

• A window is two markers, a left edge and a right edge, with the characters between them.
• Remember the window’s characters in a set. A set is a bag that holds each item only once.

How it works:

• Move the right edge forward one step to grow the window.
• If the new character is already in the set, a repeat just entered.
• Then move the left edge forward, removing characters, until the repeat is gone.
• Add the new character and check the window size.
• Keep the biggest size you ever saw.

Why it is fast:

• Each character enters once and leaves once.
• You touch every character at most twice.
• One smooth pass, so O(n).

Here is the window expanding then shrinking as it slides across "abcabcbb".

Steps to Solve

1. Set the left edge at the start. Keep an empty set for characters in the window.
2. Move the right edge across the string one character at a time.
3. If the new character is already in the set, remove characters from the left until it is gone.
4. Add the new character to the set.
5. Measure the window size, which is right minus left plus one. Keep the biggest.
6. When the right edge reaches the end, return the biggest size you saw.

#include <stdio.h>
#include <string.h>

int lengthOfLongestSubstring(const char *s) {
    int lastSeen[256];           // last index where a char was seen
    for (int i = 0; i < 256; i++) lastSeen[i] = -1;

    int left = 0, best = 0;
    int n = (int)strlen(s);
    for (int right = 0; right < n; right++) {
        unsigned char c = (unsigned char)s[right];
        if (lastSeen[c] >= left) {     // repeat is inside the window
            left = lastSeen[c] + 1;    // jump left past the old copy
        }
        lastSeen[c] = right;           // record this position
        int size = right - left + 1;   // current window size
        if (size > best) best = size;
    }
    return best;
}

int main(void) {
    const char *s = "abcabcbb";
    printf("%d\n", lengthOfLongestSubstring(s));
    return 0;
}

3

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int lengthOfLongestSubstring(const string &s) {
    unordered_set<char> window;  // characters currently in the window
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        while (window.count(s[right])) {   // repeat found
            window.erase(s[left]);         // drop the leftmost char
            left++;                        // shrink from the left
        }
        window.insert(s[right]);           // add the new char
        best = max(best, right - left + 1);
    }
    return best;
}

int main() {
    string s = "abcabcbb";
    cout << lengthOfLongestSubstring(s) << endl;
    return 0;
}

3

import java.util.HashSet;
import java.util.Set;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> window = new HashSet<>();  // chars in the window
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            while (window.contains(s.charAt(right))) {  // repeat found
                window.remove(s.charAt(left));          // drop leftmost
                left++;                                 // shrink left
            }
            window.add(s.charAt(right));                // add new char
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s));
    }
}

3

def length_of_longest_substring(s):
    window = set()        # characters currently in the window
    left = 0              # left edge of the window
    best = 0              # longest size seen so far
    for right in range(len(s)):
        while s[right] in window:     # repeat is inside the window
            window.remove(s[left])    # drop the leftmost character
            left += 1                 # shrink from the left
        window.add(s[right])          # add the new character
        best = max(best, right - left + 1)  # update the best size
    return best


s = "abcabcbb"
print(length_of_longest_substring(s))

3

function lengthOfLongestSubstring(s) {
  const window = new Set(); // characters currently in the window
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    while (window.has(s[right])) {   // repeat is inside the window
      window.delete(s[left]);        // drop the leftmost character
      left++;                        // shrink from the left
    }
    window.add(s[right]);            // add the new character
    best = Math.max(best, right - left + 1);
  }
  return best;
}

const s = "abcabcbb";
console.log(lengthOfLongestSubstring(s));

3

Let us walk through the Python version line by line and see why each line is there.

window = set() makes an empty set. This holds the characters that are inside the window right now. We use a set because checking “is this char already here” is almost instant.

left = 0 is the left edge of the window. The window is everything from left up to the current right.

best = 0 remembers the longest window we have seen so far. We return this at the end.

for right in range(len(s)): moves the right edge across the string. Each loop adds one new character to consider.

while s[right] in window: checks if the new character is already inside the window. If it is, we have a repeat. The while keeps running until the repeat is fully gone.

window.remove(s[left]) drops the character at the left edge. left += 1 then moves the left edge forward. Together these shrink the window from the left side. We keep doing this until the repeat disappears.

window.add(s[right]) adds the new character now that the window is clean.

best = max(best, right - left + 1) measures the current window size. The size is right - left + 1. We keep the bigger of the old best and this size.

return best gives back the length of the longest clean window.

⏱️ Time and Space Complexity

The brute force checks every substring, so it is slow and grows as O(n²) or worse. The sliding window touches each character at most twice, once when it enters and once when it leaves. So it runs in O(n) time. The extra memory holds the characters of the window, which is at most the number of different characters.

🧩 Key Takeaways

• ✅ A window is two edges with the characters between them. You grow the right and shrink the left.
• ✅ A set tells you instantly if a character is already inside the window.
• ✅ When a repeat enters, move the left edge forward until the repeat is gone.
• ✅ Each character enters once and leaves once, so the whole thing runs in O(n).
• ✅ Say the brute force out loud first, then explain how the window removes the repeated work.

🚀 What’s Next?

• Longest Repeating Character Replacement
• Permutation in String