Sliding window practice

Implement max sum subarray of size k, longest substring without repeating characters, and minimum window substring.

Three problems that cover the full range of window techniques. The first is fixed; the next two are variable and grow in bookkeeping complexity.

Three sliding window implementations

Python — editable, runs in your browser

# ── 1. Max sum subarray of size k (fixed window) ─────────────────────────────

def max_sum_subarray(nums, k):
  if not nums or k > len(nums):
      return 0
  window_sum = sum(nums[:k])
  best = window_sum
  for i in range(k, len(nums)):
      window_sum += nums[i] - nums[i - k]
      if window_sum > best:
          best = window_sum
  return best

# ── 2. Longest substring without repeating characters (variable window) ───────
# last_seen[ch] stores the most recent index where ch appeared.
# When right lands on a repeated character, jump left past the previous
# occurrence rather than crawling one step at a time.

def longest_no_repeat(s):
  last_seen = {}
  left = 0
  best = 0
  for right, ch in enumerate(s):
      if ch in last_seen and last_seen[ch] >= left:
          left = last_seen[ch] + 1  # jump left past the duplicate
      last_seen[ch] = right
      if right - left + 1 > best:
          best = right - left + 1
  return best

# ── 3. Minimum window substring ───────────────────────────────────────────────
# Find the shortest substring of s that contains all characters of t
# (including duplicates). Expand right until all required chars are present,
# then shrink left as far as possible while the window remains valid.

from collections import Counter

def min_window_substring(s, t):
  if not t or not s:
      return ""
  need = Counter(t)
  have = {}
  formed = 0          # how many chars currently satisfy their required count
  required = len(need)
  left = 0
  best = (float("inf"), 0, 0)  # (length, left, right)

for right, ch in enumerate(s):
      have[ch] = have.get(ch, 0) + 1
      if ch in need and have[ch] == need[ch]:
          formed += 1

while formed == required:   # window is valid — try to shrink
          if right - left + 1 < best[0]:
              best = (right - left + 1, left, right)
          left_ch = s[left]
          have[left_ch] -= 1
          if left_ch in need and have[left_ch] < need[left_ch]:
              formed -= 1
          left += 1

return s[best[1]:best[2] + 1] if best[0] != float("inf") else ""

# ── Demo ──────────────────────────────────────────────────────────────────────
print("Max sum k=3:", max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9
print("Max sum k=2:", max_sum_subarray([2, 3, 4, 1, 5], 2))     # 7

print()
print("No repeat 'abcabcbb':", longest_no_repeat("abcabcbb"))    # 3
print("No repeat 'pwwkew':", longest_no_repeat("pwwkew"))        # 3
print("No repeat 'bbbbb':", longest_no_repeat("bbbbb"))          # 1

print()
print("Min window 'ADOBECODEBANC' for 'ABC':", min_window_substring("ADOBECODEBANC", "ABC"))  # BANC
print("Min window 'a' for 'a':", min_window_substring("a", "a"))                              # a
print("Min window 'a' for 'aa':", min_window_substring("a", "aa"))                            # ""

Key implementation notes

Longest no-repeat — jump, don't crawl. Storing the last-seen index lets the left pointer jump directly past the duplicate instead of stepping one character at a time. Both give the same result, but the jump version is faster in practice (though both remain O(n) — each character is visited at most twice).

Minimum window — formed counter avoids re-scanning. Checking whether the window is currently valid by iterating over all required characters every step would cost O(|t|) per step. The formed variable tracks how many character requirements are currently satisfied in O(1) per character event.

Minimum window substring is the hardest of the three. The bookkeeping is richer but the structure is identical: expand right to include a new character, update state, then shrink left while the window is still valid. The same loop appears in every variable-window problem.

Where to go next

Next: two-pointer on strings — a complementary technique where the two pointers start at opposite ends and move inward, rather than both advancing from left to right.

Finished reading? Mark it complete to track your progress.

Three sliding window implementations

Key implementation notes

Where to go next

On this page