Longest Substring Without Repeating Characters — Sliding Window [Google, Amazon, Meta]

Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

Input: "abcabcbb" → 3 (substring "abc") Input: "pwwkew" → 3 (substring "wke")

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n) time, O(min(m,n)) space where m = charset size

Intuition

Sliding window with last_seen HashMap. When we encounter a repeated character, jump left to last_seen[char]+1 (no need to shrink one by one).

last = {}  # char → last index
left = 0, best = 0
for right, c in enumerate(s):
    if c in last and last[c] >= left:
        left = last[c] + 1   # jump past the previous occurrence
    last[c] = right
    best = max(best, right - left + 1)

C++ Solution

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> last;
        int left = 0, best = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            if (last.count(s[r]) && last[s[r]] >= left)
                left = last[s[r]] + 1;
            last[s[r]] = r;
            best = max(best, r - left + 1);
        }
        return best;
    }
};

Java Solution

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

Python Solution

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

JavaScript Solution

function lengthOfLongestSubstring(s) {
    const last = new Map();
    let left = 0, best = 0;
    for (let r = 0; r < s.length; r++) {
        if (last.has(s[r]) && last.get(s[r]) >= left)
            left = last.get(s[r]) + 1;
        last.set(s[r], r);
        best = Math.max(best, r - left + 1);
    }
    return best;
}