Longest Substring Without Repeating Characters

medium string sliding window

Problem

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

Use a sliding window [l, r]. Walk r forward; if the character at r is already inside the window, jump l to one past the previous position of that character. The window is always duplicate-free.

Inputs = "abcadcbe"

Output5

"adcbe" (positions 3..7) has all distinct characters and length 5.

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

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

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

int lengthOfLongestSubstring(const string& s) {
    unordered_map<char, int> last;
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        char ch = s[r];
        auto it = last.find(ch);
        if (it != last.end() && it->second >= l) l = it->second + 1;
        last[ch] = r;
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
}

Explanation

We want the longest stretch of characters with no repeats. Checking every possible substring would be slow, so instead we keep a sliding window — a range [l, r] that always stays duplicate-free.

The right edge r moves forward one character at a time, growing the window. We remember the last position we saw each character using a small lookup table.

If the new character is already inside the window, we have a repeat. To fix it, we jump the left edge l to just past where that character appeared before, which kicks the duplicate out.

After every step the window [l, r] is valid, so we record its length and keep the best one seen.

Example: in "abcabcbb" the window grows to "abc" (length 3); when the second a arrives, l slides right to drop the old a, and the search continues. The answer is 3.

Time: O(n) Space: O(min(n, alphabet))