Why does this sliding window count too many substrings?

programming web dev
1

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.

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

2

@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:


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