Longest Substring Without Repeating Characters — Sliding Window

This is the prototypical sliding window problem and one of the highest-yield patterns for string interview questions. If you internalize this one, half the medium-tier string problems become muscle memory.

The Problem

Given a string s, find the length of the longest substring that contains no repeated characters.

Example:

Input:  s = "abcabcbb"
Output: 3
Explanation: "abc" has length 3.

“Substring” means contiguous. “Subsequence” would be a different and much harder problem.

Intuition

The brute force tries every substring and checks for uniqueness — O(n^2) in practice with early break, O(n^3) naively. For n = 5 * 10^4, the quadratic version is borderline.

The optimal idea is a sliding window with a hash map from character to its most recent index. As we advance the right edge, if the character has been seen inside the current window, jump the left edge just past the previous occurrence. The window always contains unique characters; it expands on the right and contracts on the left only when needed.

The subtle bit is the guard last[ch] >= left. A character could have been seen long ago but already excluded from the current window, in which case it does not constrain us.

Explanation with Example

Take s = "abcabcbb".

• right = 0, ch = ‘a’. last = {a: 0}. window “a”, best = 1.
• right = 1, ch = ‘b’. last = {a: 0, b: 1}. window “ab”, best = 2.
• right = 2, ch = ‘c’. last = {a: 0, b: 1, c: 2}. window “abc”, best = 3.
• right = 3, ch = ‘a’. Seen at 0 >= left (0). left = 1. window “bca”, best = 3.
• right = 4, ch = ‘b’. Seen at 1 >= left (1). left = 2. window “cab”, best = 3.
• right = 5, ch = ‘c’. Seen at 2 >= left (2). left = 3. window “abc”, best = 3.
• right = 6, ch = ‘b’. Seen at 4 >= left (3). left = 5. window “cb”, best = 3.
• right = 7, ch = ‘b’. Seen at 6 >= left (5). left = 7. window “b”, best = 3.

Return 3.

index    0 1 2 3 4 5 6 7
char     a b c a b c b b

step 3:  [a b c] a b c b b   width 3
step 4:    [b c a] b c b b   left jumped 0 -> 1
step 5:      [c a b] c b b   left jumped 1 -> 2
step 7:              [c b]   left jumped to 5

Code

def length_of_longest_substring(s):
    last = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (last.containsKey(ch) && last.get(ch) >= left) {
                left = last.get(ch) + 1;
            }
            last.put(ch, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> last;
        int left = 0, best = 0;
        for (int right = 0; right < (int)s.size(); ++right) {
            char ch = s[right];
            auto it = last.find(ch);
            if (it != last.end() && it->second >= left) {
                left = it->second + 1;
            }
            last[ch] = right;
            best = max(best, right - left + 1);
        }
        return best;
    }
};

Edge Cases

• Empty string. Return 0. The loop never executes.
• All identical characters like "aaaa". The window stays width 1.
• All unique characters. The window grows to the full string.
• Strings with spaces, digits, punctuation. The algorithm is character-agnostic.
• Unicode. Python handles unicode strings transparently; the hash map keys are code points.

Complexity Analysis

• Time: O(n). Each character is visited once by the right pointer. left only advances, never retreats, so the work is linear.
• Space: O(min(n, alphabet)) for the hash map. For ASCII this is O(1) bounded by 128 or 256.

How to Explain It in an Interview

• Restate the problem and confirm substring versus subsequence.
• Quote the O(n^2) brute force in one sentence and move on.
• Sketch the sliding window: a window that always contains unique characters, expanded on the right and contracted on the left only when needed.
• Justify the use of a hash map of last-seen indices so that contraction is O(1) instead of a linear scan.
• Walk through the last[ch] >= left guard. This is the bug source for most candidates.
• State O(n) time and bounded space.

Related Problems

• Longest Substring with At Most Two Distinct Characters
• Longest Substring with At Most K Distinct Characters
• Minimum Window Substring
• Permutation in String
• Longest Repeating Character Replacement

The whole pattern family is in sliding window technique, and the hash map mechanics come from hashing and hash maps.

Wrap up

This problem rewards a clean sliding window template more than any clever trick. Write the skeleton, “expand right, contract left on violation, update answer”, and almost every variable-size window problem falls out of it.