awelgorithms

Track the best valid length

Updated

Keep bestLen. When the window is valid, bestLen = max(bestLen, R-L+1). Init bestLen to 0 if empty is allowed.

What to focus on

Window constraint: longest window with all unique values. Update bestLen only on unique windows. Length is R-L+1, not R-L. Ties leave bestLen unchanged.

Worked examples

best 3

s = "abca"
  1. abc length 3 → best=3
  2. bca length 3 → best stays 3

Result: bestLen = 3

best 3 then 2

a = [4, 1, 9, 1]
  1. [4,1,9] unique length 3 → best=3
  2. after shrink [9,1] unique length 2
  3. 2 < 3 so best stays 3

Result: bestLen = 3

best 1

a = [7]
  1. [7] unique length 1
  2. init 0 then max(0,1)

Result: bestLen = 1

Try it

Write bestUniqueLen(a). a is an array of integers, or s is a string. L is the left index. R is the right index. The window includes a[L..R]. Valid means all unique. Return the final bestLen. Ties leave bestLen unchanged. On s="abca"; a=[4, 1, 9, 1]; a=[7].

a (or s) is nonempty.

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

LeetCode problems that use this skill