awelgorithms

Unique-character window shrinks on a repeat

Updated

When s[R] already has count 1 in the window, the new count is 2. Shrink L until that character's count is 1, usually L moves to lastIndex[s[R]]+1.

What to focus on

The repeat is the trigger. Do not shrink on a fresh character. After the shrink, every count is 1 again and R can stay.

Worked examples

second a

s = "abca", R=3
  1. window was "abc", cnt[a]=1
  2. s[3]='a' → 2
  3. drop s[0]='a' → 1, L=1

Result: "bca" unique

abcabcbb

s = "abcabcbb", R=3
  1. s[3]='a' repeats s[0]
  2. L moves to 1
  3. window "bca"

Result: shrink on the repeat, not before

late bb

s = "abcabcbb", R=7
  1. s[7]='b' repeats the b already in the window
  2. shrink until one b remains

Result: window "b" at the end

Try it

Write uniqueShrinkOnRepeat(s). s is a string. R is the current right index that repeats a character still inside [L, R]. L is the left index. The window includes s[L..R]. At each R print whether you shrunk and the new L. Return nothing. On "abca" and "abcabcbb".

s is nonempty. The current R repeats a character still inside [L, R].

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

LeetCode problems that use this skill