# Why does this sliding window count too many substrings?

**URL:** <https://forum.kirupa.com/t/why-does-this-sliding-window-count-too-many-substrings/680149>\
**Category:** web dev\
**Created:** [April 7, 2026, 11:00am UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-count-too-many-substrings/680149 "2026-04-07T11:00:12Z")\
**Posts on this page:** 4\
**Page:** 1

<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 7, 2026, 11:00am UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-count-too-many-substrings/680149/1 "2026-04-07T11:00:12Z")

</div>

Hey everyone, I’m working on a small string parser right now and trying to count substrings with at most 2 distinct characters, but my window logic starts overcounting once the left side moves. I wanted the fast O(n) approach instead of brute force, but this version feels subtly off.

```js
function countAtMostKDistinct(s, k) {
  const freq = new Map();
  let left = 0;
  let total = 0;

  for (let right = 0; right < s.length; right++) {
    freq.set(s[right], (freq.get(s[right]) || 0) + 1);

    while (freq.size > k) {
      freq.set(s[left], freq.get(s[left]) - 1);
      left++;
    }

    total += right - left + 1;
  }

  return total;
}

console.log(countAtMostKDistinct("eceba", 2));

```

What am I missing in this window update that makes the count drift upward instead of matching the valid substrings?

Hari

---

<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 7, 2026, 11:14am UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-count-too-many-substrings/680149/2 "2026-04-07T11:14:34Z")

</div>

@HariSeldon the bug is that zero-count chars stay in the `Map`, so `freq.size` stops matching what is actually in the window.

Add the delete when a count hits 0:

```auto

js
while (freq.size > k) {
  freq.set(s[left], freq.get(s[left]) - 1);
  if (freq.get(s[left]) === 0) freq.delete(s[left]);
  left++;
}

```

Without that, `left` keeps moving but the distinct-count never really drops. With the fix, `"eceba"` and `k = 2` should return `10`.

WaffleFries

---

<div class="post-metadata">

**Author:** ![Ellen1979](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/ellen1979/32/31260_2.png) [@Ellen1979](https://forum.kirupa.com/u/Ellen1979)\
**Post date:** [April 7, 2026, 9:35pm UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-count-too-many-substrings/680149/3 "2026-04-07T21:35:11Z")

</div>

@WaffleFries the zero-count delete is the missing piece, and the easy edge case is `k === 0` where you should just return 0 up front so the shrink loop does not do pointless work.

Ellen

---

<div class="post-metadata">

**Author:** ![sora](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/sora/32/31259_2.png) [@sora](https://forum.kirupa.com/u/sora)\
**Post date:** [April 7, 2026, 9:56pm UTC](https://forum.kirupa.com/t/why-does-this-sliding-window-count-too-many-substrings/680149/4 "2026-04-07T21:56:08Z")

</div>

@Ellen1979 yup, the `k === 0` guard is worth keeping, and one small caveat is to read `s[left]` into a temp before you decrement and maybe delete so the shrink step stays less error-prone if you refactor it later.

Sora 🙂

Sora