awelgorithms

Longest valid window expands greedily

Updated

For a longest-window problem, advance R whenever you can. Shrink L only when the new R makes the window invalid. Do not shrink a still-valid window to tidy it.

What to focus on

Best length is the maximum R-L+1 among windows that passed the constraint. A shorter valid window inside a longer valid one is not better.

Worked examples

unique grow

s = "abca"
  1. R=0,1,2 "abc" unique, keep expanding
  2. do not shrink at R=2

Result: length 3 still valid

zeros grow

a = [1, 0, 0, 1, 9], k=1 zeros
  1. [1,0] zeros 1, still expand R
  2. invalid only when the second 0 enters

Result: greedy expand until zeros>1

product grow

a = [1, 2, 3, 4], limit 10
  1. [1] then [1,2] then [1,2,3] all prod<10
  2. stop expanding only after *4 breaks it

Result: longest valid 3

Try it

Write expandGreedy(a). a is an array of integers, or s is a string. R is the right index. Expand R while the window stays valid. The window includes a[L..R]. Print every R where you expand without shrinking. Return nothing. On "abca" unique, [1, 0, 0, 1, 9] k=1 zeros, and [1, 2, 3, 4] prod<10.

a (or s) is nonempty. Product cases use positive integers. A valid window exists.

practise it with Awel find your weak spots: free skill check

LeetCode problems that use this skill