Longest Substring Without Repeating Characters

Problem

Find the length of the longest substring without repeating characters.

Input:  s = "abcabcbb"
Output: 3   ("abc")

Python Solution

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

C++ Solution

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> lastSeen;
    int start = 0, best = 0;
    for (int i = 0; i < s.size(); i++) {
        if (lastSeen.count(s[i]) && lastSeen[s[i]] >= start) {
            start = lastSeen[s[i]] + 1;
        }
        lastSeen[s[i]] = i;
        best = max(best, i - start + 1);
    }
    return best;
}

Java Solution

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

Complexity

Time: O(n) — the sliding window's start pointer only ever moves forward, so each character is processed a constant number of times. Space: O(min(n, alphabet size)) for the last-seen index map.