Why does this sliding-window check miss some shortest matching substrings?

programming web dev
1

I’m trying to find the smallest substring of s that contains all chars from t with counts. This works on some cases but misses shorter windows when duplicates are involved. What is wrong with my window-shrinking logic?

function minWin(s, t) {
  const need = new Map(), have = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let formed = 0, left = 0, best = '';
  for (let right = 0; right < s.length; right++) {
    const c = s[right]; have.set(c, (have.get(c) || 0) + 1);
    if (have.get(c) >= (need.get(c) || 0)) formed++;
    while (formed === need.size) {
      const win = s.slice(left, right + 1);
      if (!best || win.length < best.length) best = win;
      have.set(s[left], have.get(s[left]) - 1); left++;
    }
  }
  return best;
}

Arthur

2

@ArthurDent, the bug is that formed bumps on `>=

, so the same needed char can increment it multiple times, and your shrink loop never decrements it when dropping below the required count;
track

formedonly when a char hitsneed.get(c)exactly, then subtract when movingleftmakeshave.get(ch) < need.get(ch). That tradeoff makes the bookkeeping a hair stricter, but it fixes duplicate-heavy cases like t = “AABC”` without overcounting.

WaffleFries

3

Another good way to spot it: log (left, right, formed, ch, have.get(ch), need.get(ch)) each time the window shrinks; in duplicate-heavy cases like t = "AABC", you’ll see a window stop being valid one step before formed admits it.

if (need.has(c) && have.get(c) === need.get(c)) formed++;

// when shrinking
const ch = s[left];
if (need.has(ch) && have.get(ch) === need.get(ch)) formed--;
have.set(ch, have.get(ch) - 1);
left++;

That keeps formed tied to “this character requirement is satisfied exactly,” instead of letting the same needed char vote twice and wander off with the election.

Arthur :grinning_face:

4

@ArthurDent the t = "AABC" case is the giveaway because formed is tracking hits, not satisfied character buckets, so one extra A can mask that C just fell short during shrink.

Hari