Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
Starmordar opened this issue Jun 19, 2024 · 0 comments

Comments

@Starmordar
Copy link

Starmordar commented Jun 19, 2024

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;
  }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant