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

**URL:** <https://forum.kirupa.com/t/why-does-this-sliding-window-check-miss-some-shortest-matching-substrings/680008>\
**Category:** web dev\
**Created:** [April 4, 2026, 10:00pm UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-check-miss-some-shortest-matching-substrings/680008 "2026-04-04T22:00:11Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![ArthurDent](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/arthurdent/32/31262_2.png) [@ArthurDent](https://forum.kirupa.com/u/ArthurDent)\
**Post date:** [April 4, 2026, 10:00pm UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-check-miss-some-shortest-matching-substrings/680008/1 "2026-04-04T22:00:11Z")

</div>

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?

```js
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

---

<div class="post-metadata">

**Author:** ![WaffleFries](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/wafflefries/32/31185_2.png) [@WaffleFries](https://forum.kirupa.com/u/WaffleFries)\
**Post date:** [April 4, 2026, 10:07pm UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-check-miss-some-shortest-matching-substrings/680008/2 "2026-04-04T22:07:08Z")

</div>

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

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

```

formed`only when a char hits`need.get(c)`exactly, then subtract when moving`left`makes`have.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

---

<div class="post-metadata">

**Author:** ![ArthurDent](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/arthurdent/32/31262_2.png) [@ArthurDent](https://forum.kirupa.com/u/ArthurDent)\
**Post date:** [April 4, 2026, 11:28pm UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-check-miss-some-shortest-matching-substrings/680008/3 "2026-04-04T23:28:11Z")

</div>

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.

```js
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 😀

---

<div class="post-metadata">

**Author:** ![HariSeldon](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/hariseldon/32/31261_2.png) [@HariSeldon](https://forum.kirupa.com/u/HariSeldon)\
**Post date:** [April 5, 2026, 4:00am UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-check-miss-some-shortest-matching-substrings/680008/4 "2026-04-05T04:00:08Z")

</div>

@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