Longest Substring Sliding Window: Shrink While Invalid, and Why It Works

The rule that makes it work

The longest-window template is correct when validity survives shrinking: every run inside a valid run is valid. "At most k distinct letters", "at most k zeros", "sum at most B with positive numbers" and "no repeated letter" all qualify.

Under that rule, for a fixed right end hi the valid starts are a block [s, hi], and the longest valid window ending at hi starts at s. When hi moves right, s cannot move left: a window starting before s and ending later would contain the invalid window [s − 1, hi]. So lo only ever moves forward, each index enters and leaves once, and the scan is linear.

The longest run with at most 2 distinct letters in "abaccc".

Step 1 / 6

s
a0lo/hib1a2c3c4c5
countsa×1best1
'a' enters; the window has 1 distinct letter. New longest: 1.
Step 2 / 6

s
a0lob1hia2c3c4c5
countsa×1 b×1best2
'b' enters; the window has 2 distinct letters. New longest: 2.
Step 3 / 6

s
a0lob1a2hic3c4c5
countsa×2 b×1best3
'a' enters; the window has 2 distinct letters. New longest: 3.
Step 4 / 6

s
a0b1a2loc3hic4c5
countsa×1 c×1best3
'c' enters; the window has 3 distinct letters. That is more than 2, so drop 'a', 'b' from the left until one letter disappears.
Step 5 / 6

s
a0b1a2loc3c4hic5
countsa×1 c×2best3
'c' enters; the window has 2 distinct letters.
Step 6 / 6

s
a0b1a2loc3c4c5hi
countsa×1 c×3best4
'c' enters; the window has 2 distinct letters. New longest: 4.

The code

A map from letter to count is the state; its number of keys is the number of distinct letters. The shrinking is a while, not an if: one removal does not always remove a letter entirely.

from collections import defaultdict

def longest_k_distinct(s, k):
    count = defaultdict(int)          # letter -> copies inside the window
    best = lo = 0
    for hi, c in enumerate(s):
        count[c] += 1
        while len(count) > k:         # too many kinds: shrink from the left
            count[s[lo]] -= 1
            if count[s[lo]] == 0:
                del count[s[lo]]
            lo += 1
        best = max(best, hi - lo + 1)
    return best

#include <string>
#include <array>
#include <algorithm>

int solve(const std::string& s, int k) {
    std::array<int, 256> count{};                 // letter -> copies inside the window
    int kinds = 0, best = 0, lo = 0;
    for (int hi = 0; hi < (int)s.size(); ++hi) {
        if (count[(unsigned char)s[hi]]++ == 0) ++kinds;
        while (kinds > k) {                       // too many kinds: shrink from the left
            if (--count[(unsigned char)s[lo]] == 0) --kinds;
            ++lo;
        }
        best = std::max(best, hi - lo + 1);
    }
    return best;
}

class Solution {
    public int longestKDistinct(String s, int k) {
        int[] count = new int[256];                  // letter -> copies inside the window
        int kinds = 0, best = 0, lo = 0;
        for (int hi = 0; hi < s.length(); hi++) {
            if (count[s.charAt(hi)]++ == 0) kinds++;
            while (kinds > k) {                      // too many kinds: shrink from the left
                if (--count[s.charAt(lo)] == 0) kinds--;
                lo++;
            }
            best = Math.max(best, hi - lo + 1);
        }
        return best;
    }
}

function longestKDistinct(s, k) {
  const count = new Map();             // letter -> copies inside the window
  let best = 0, lo = 0;
  for (let hi = 0; hi < s.length; hi++) {
    count.set(s[hi], (count.get(s[hi]) || 0) + 1);
    while (count.size > k) {           // too many kinds: shrink from the left
      const n = count.get(s[lo]) - 1;
      if (n === 0) count.delete(s[lo]); else count.set(s[lo], n);
      lo++;
    }
    best = Math.max(best, hi - lo + 1);
  }
  return best;
}

fn solve(s: &str, k: usize) -> usize {
    let b = s.as_bytes();
    let mut count = [0usize; 256];                   // letter -> copies inside the window
    let (mut kinds, mut best, mut lo) = (0usize, 0usize, 0usize);
    for hi in 0..b.len() {
        if count[b[hi] as usize] == 0 { kinds += 1; }
        count[b[hi] as usize] += 1;
        while kinds > k {                            // too many kinds: shrink from the left
            count[b[lo] as usize] -= 1;
            if count[b[lo] as usize] == 0 { kinds -= 1; }
            lo += 1;
        }
        best = best.max(hi + 1 - lo);
    }
    best
}

import qualified Data.Map.Strict as M

-- The window is the original string from its left end (so shrinking is dropping the head), its length and its counts.
solve :: String -> Int -> Int
solve s k = go s s 0 M.empty 0
  where
    go [] _ _ _ best = best
    go (c:rest) win len m best =
      let m1 = M.insertWith (+) c 1 m
          (win', len', m') = shrink win (len + 1) m1
      in go rest win' len' m' (max best len')
    shrink win len m
      | M.size m <= k = (win, len, m)
      | otherwise = case win of
          (x:xs) -> shrink xs (len - 1) (M.update (\n -> if n == 1 then Nothing else Just (n - 1)) x m)
          [] -> ([], 0, m)

The same code is the reference solution to Longest run with at most k distinct letters, where it is compiled and run against the tests in all six languages.

Rephrase the operation as a property

Many longest-window questions describe an operation rather than a property: flip at most k zeros, replace at most k letters, delete one element. The first step is always to restate it as a property of a contiguous run, and then the template applies unchanged.

The question says	A run is valid when	State
flip at most k zeros to ones	it holds at most k zeros	a zero counter
delete exactly one element	it holds at most one zero; the answer is its length minus 1	a zero counter
replace at most k letters	length − (count of its most common letter) ≤ k	26 counts and the largest count
no repeated letters	every count is at most 1	last index of each letter
fit within a time budget	its total is at most the budget (positive times)	the running total

Sliding instead of shrinking

In the replacement problem the test needs the window's most common letter, and that count can fall when a letter leaves. Recomputing it over 26 letters is fine. But there is a neater argument: the answer only improves when some letter reaches a count larger than any seen before, so keep top as the largest count ever seen and never lower it. When the window needs more than k changes, move lo by exactly one step. The window then never shrinks; it slides at the best length found so far, and grows only when a better window genuinely exists. Its final length is the answer.

The longest run of one letter after at most 1 change in "AABABBA".

Step 1 / 7

s
A0lo/hiA1B2A3B4B5A6
top1length1
'A' enters. The largest count seen is 1; the window of length 1 needs 0 changes.
Step 2 / 7

s
A0loA1hiB2A3B4B5A6
top2length2
'A' enters. The largest count seen is 2; the window of length 2 needs 0 changes.
Step 3 / 7

s
A0loA1B2hiA3B4B5A6
top2length3
'B' enters. The largest count seen is 2; the window of length 3 needs 1 change.
Step 4 / 7

s
A0loA1B2A3hiB4B5A6
top3length4
'A' enters. The largest count seen is 3; the window of length 4 needs 1 change.
Step 5 / 7

s
A0A1loB2A3B4hiB5A6
top3length4
'B' enters. The largest count seen is 3; the window of length 5 needs 2 changes. That is more than 1, so slide: drop 'A' and keep the length at 4.
Step 6 / 7

s
A0A1B2loA3B4B5hiA6
top3length4
'B' enters. The largest count seen is 3; the window of length 5 needs 2 changes. That is more than 1, so slide: drop 'A' and keep the length at 4.
Step 7 / 7

s
A0A1B2A3loB4B5A6hi
top3length4
'A' enters. The largest count seen is 3; the window of length 5 needs 2 changes. That is more than 1, so slide: drop 'B' and keep the length at 4. The window never shrank, so its final length, 4, is the answer.

TimeO(n)

SpaceO(1)

The window's contents may not be a valid answer at the end, only its length is. If you need the substring, record it when the length grows.

The longest valid window

The rule that makes it work

The code

Rephrase the operation as a property

Sliding instead of shrinking

Problems in this module