neetcode-gh / leetcode

Leetcode solutions
MIT License
5.55k stars 2.29k forks source link

Solution 'Accepted' for 'Minimum Window Substring' but fails LeetCode tests #3504

Open Starmordar opened 3 months ago

Starmordar commented 3 months ago

The current test cases for 'Minimum Window Substring' might not cover all edge cases.

Input: s = "aaaaaaaaaaaabbbbbcdd',  t = 'abcdd'
Expected Output: "abbbbbcdd"

My solution is accepted despite returning "" for this test case.

class Solution {
  /**
   * @param {string} s
   * @param {string} t
   * @return {string}
   */
  minWindow(s, t) {
    if (t.length > s.length) return '';

    let substring = '';
    const map = new Map();
    const set = new Set();

    for (let i = 0; i < t.length; i++) {
      map.set(t[i], (map.get(t[i]) ?? 0) + 1);
      set.add(t[i]);
    }

    let startIndex = 0;
    for (let endIndex = 0; endIndex < s.length; endIndex++) {
      if (!map.has(s[endIndex])) continue;

      const nextCount = map.get(s[endIndex]) - 1;
      map.set(s[endIndex], nextCount);

      if (nextCount === 0) set.delete(s[endIndex]);
      else set.add(s[endIndex]);

      while (map.get(s[startIndex]) < 0 || (!map.has(s[startIndex]) && startIndex < endIndex)) {
        if (map.get(s[startIndex]) < 0) {
          const nextCount = map.get(s[startIndex]) + 1;
          map.set(s[startIndex], nextCount);

          if (nextCount === 0) set.delete(s[startIndex]);
        }
        startIndex++;
      }

      if (
        set.size === 0 &&
        (substring.length === 0 || endIndex + 1 - startIndex < substring.length)
      ) {
        substring = s.slice(startIndex, endIndex + 1);
      }
    }

    return substring;
  }
}