Sliding Window

Expand right freely, shrink left when the window becomes invalid

Sliding window turns O(n²) substring/subarray problems into O(n). The template: grow the right edge unconditionally, then shrink the left edge until the window satisfies the constraint again.

Language:

Python

All languages — Variable-size window

JavaScript

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

console.log(longestNoRepeat("abcabcbb")); // 3

TypeScript

function longestNoRepeat(s: string): number {
  const seen = new Map<string, number>();
  let best = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (seen.has(c) && seen.get(c)! >= left)
      left = seen.get(c)! + 1;
    seen.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Java

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

func longestNoRepeat(s string) int {
    seen := make(map[rune]int)
    best, left := 0, 0
    for right, c := range s {
        if idx, ok := seen[c]; ok && idx >= left {
            left = idx + 1
        }
        seen[c] = right
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

C++

int longestNoRepeat(string s) {
    unordered_map<char,int> seen;
    int best = 0, left = 0;
    for (int right = 0; right < s.size(); right++) {
        char c = s[right];
        if (seen.count(c) && seen[c] >= left)
            left = seen[c] + 1;
        seen[c] = right;
        best = max(best, right - left + 1);
    }
    return best;
}