# Sliding Window — Part 2: Interview Problems

Six problems: fixed windows, 'longest valid' windows and 'shortest valid' windows, ending with the classic hard Minimum Window Substring.

## 1. Best Time to Buy and Sell Stock (LeetCode 121)

**🟢 Easy.** `prices[i]` is a stock's price on day i. Choose one day to buy and a later day to sell; return the maximum profit (0 if none).

```text
prices = [7,1,5,3,6,4] → 5   (buy at 1, sell at 6)
```

**Approach.** Track the cheapest price so far (the best possible buy day for any sell day). For each day, profit = price − minSoFar. This is a window whose left edge jumps to the newest minimum.

**Complexity.** O(n) time, O(1) space.

```typescript
function maxProfit(prices: number[]): number {
  let minPrice = Infinity, best = 0;
  for (const p of prices) {
    minPrice = Math.min(minPrice, p);
    best = Math.max(best, p - minPrice);
  }
  return best;
}
```

```python
def max_profit(prices):
    min_price = float("inf")
    best = 0
    for p in prices:
        min_price = min(min_price, p)
        best = max(best, p - min_price)
    return best
```

## 2. Longest Substring Without Repeating Characters (LeetCode 3)

**🟠 Medium.** Return the length of the longest substring of `s` with no repeated characters.

```text
s = "abcabcbb" → 3   ("abc")
```

**Approach.** Variable window with a map from character to its last index. When `s[right]` already occurs inside the window, jump `left` past its previous occurrence.

**Complexity.** O(n) time, O(min(n, alphabet)) space.

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

```python
def length_of_longest_substring(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
```

## 3. Longest Repeating Character Replacement (LeetCode 424)

**🟠 Medium.** You may replace at most `k` characters of `s`. Return the length of the longest substring of one repeated letter you can get.

```text
s = "AABABBA", k = 1 → 4
```

**Approach.** A window is valid when `length − maxFreq ≤ k` (everything except the most frequent letter gets replaced). Expand right, update counts and `maxFreq`; while invalid, shrink left. `maxFreq` never needs to decrease: a smaller maxFreq can't produce a longer answer than one already found.

**Complexity.** O(n) time, O(26) space.

```typescript
function characterReplacement(s: string, k: number): number {
  const counts = new Map<string, number>();
  let left = 0, maxFreq = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) ?? 0) + 1);
    maxFreq = Math.max(maxFreq, counts.get(s[right])!);
    while (right - left + 1 - maxFreq > k) {
      counts.set(s[left], counts.get(s[left])! - 1);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}
```

```python
def character_replacement(s, k):
    counts = {}
    left = max_freq = best = 0
    for right, c in enumerate(s):
        counts[c] = counts.get(c, 0) + 1
        max_freq = max(max_freq, counts[c])
        while (right - left + 1) - max_freq > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best
```

## 4. Permutation in String (LeetCode 567)

**🟠 Medium.** Return `true` if some permutation of `s1` appears as a substring of `s2`.

```text
s1 = "ab", s2 = "eidbaooo" → true   ("ba")
```

**Approach.** Fixed window of size `len(s1)` over `s2`. Keep letter counts for the window and compare with the counts of `s1`. Sliding adds one letter and removes one, so each step is O(26) (or O(1) with a 'matches' counter).

**Complexity.** O(26 · n) time, O(26) space.

```typescript
function checkInclusion(s1: string, s2: string): boolean {
  const k = s1.length;
  if (k > s2.length) return false;
  const need = new Array(26).fill(0), win = new Array(26).fill(0);
  for (const c of s1) need[c.charCodeAt(0) - 97]++;
  for (let i = 0; i < s2.length; i++) {
    win[s2.charCodeAt(i) - 97]++;
    if (i >= k) win[s2.charCodeAt(i - k) - 97]--;
    if (win.every((v, j) => v === need[j])) return true;
  }
  return false;
}
```

```python
def check_inclusion(s1, s2):
    k = len(s1)
    if k > len(s2):
        return False
    need = [0] * 26
    window = [0] * 26
    for c in s1:
        need[ord(c) - 97] += 1
    for i, c in enumerate(s2):
        window[ord(c) - 97] += 1
        if i >= k:
            window[ord(s2[i - k]) - 97] -= 1
        if window == need:
            return True
    return False
```

## 5. Minimum Size Subarray Sum (LeetCode 209)

**🟠 Medium.** Given positive integers `nums` and `target`, return the minimal length of a contiguous subarray with sum ≥ target (0 if none).

```text
target = 7, nums = [2,3,1,2,4,3] → 2   ([4,3])
```

**Approach.** 'Shortest valid' window: expand right adding to the sum; while sum ≥ target, record the length and shrink from the left. Works because all numbers are positive (shrinking always lowers the sum).

**Complexity.** O(n) time, O(1) space.

```typescript
function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0, total = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    total += nums[right];
    while (total >= target) {
      best = Math.min(best, right - left + 1);
      total -= nums[left++];
    }
  }
  return best === Infinity ? 0 : best;
}
```

```python
def min_sub_array_len(target, nums):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
```

## 6. Minimum Window Substring (LeetCode 76)

**🔴 Hard.** Return the smallest substring of `s` containing every character of `t` (with multiplicity), or `""`.

```text
s = "ADOBECODEBANC", t = "ABC" → "BANC"
```

**Approach.** Count what `t` needs. Expand right; when a character's window count reaches its need, increment `formed`. While `formed` equals the number of distinct needed characters, the window is valid: record it, then shrink from the left, decrementing `formed` when a needed count drops below its requirement.

**Complexity.** O(|s| + |t|) time, O(alphabet) space.

```typescript
function minWindow(s: string, t: string): string {
  if (!s || !t) return "";
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  const win = new Map<string, number>();
  let formed = 0, left = 0, bestLen = Infinity, bestStart = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    win.set(c, (win.get(c) ?? 0) + 1);
    if (need.has(c) && win.get(c) === need.get(c)) formed++;
    while (formed === need.size) {
      if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
      const d = s[left++];
      win.set(d, win.get(d)! - 1);
      if (need.has(d) && win.get(d)! < need.get(d)!) formed--;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
}
```

```python
def min_window(s, t):
    if not t or not s:
        return ""
    need = {}
    for c in t:
        need[c] = need.get(c, 0) + 1
    window = {}
    formed, required = 0, len(need)
    left = 0
    best_len, best_start = float("inf"), 0
    for right, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            formed += 1
        while formed == required:
            if right - left + 1 < best_len:
                best_len, best_start = right - left + 1, left
            d = s[left]
            window[d] -= 1
            if d in need and window[d] < need[d]:
                formed -= 1
            left += 1
    return "" if best_len == float("inf") else s[best_start:best_start + best_len]
```