Minimum Window Substring - JS Solution

JS
Editorial

Approach

The Minimum Window Substring problem is solved using the Sliding Window technique with two pointers (left and right) and a frequency map charNeedMap that tracks how many of each target character are still required. We maintain requiredUniqueCount and fulfilledUniqueCount to determine when the current window satisfies all required characters. The algorithm gradually expands the window by moving right to include new characters until it becomes valid — meaning all characters from t are covered. Once valid, it shrinks the window by moving left forward while the condition remains satisfied, discarding unnecessary characters to find the shortest valid substring.

  • Core data structures / variables:
    • charNeedMap: a hashmap of remaining requirements for each character in t. Initialized from frequencies of t (since the window is initially empty, every required character is still missing from the current window). A value > 0 means we still need that many of the character; a value = 0 means the requirement for that character is exactly satisfied; a value < 0 means the window currently has more than required (which is allowed).
    • left: start index of the current window.
    • right: end index of the current window.
    • requiredUniqueCount = charNeedMap.size: the number of distinct characters from t that must be fully satisfied.
    • fulfilledUniqueCount: how many of those distinct requirements are currently fully satisfied (their need count is 0).
    • minLength: length of the best (shortest) valid window found so far (start with Infinity).
    • minStart: starting index of that best window.
  • Algorithm flow:
    • Initialization: Build charNeedMap from t. Set left = 0, minLength = Infinity, minStart = 0, fulfilledUniqueCount = 0.
    • For each right from 0 to s.length - 1:
      • Let rightChar = s[right].
      • If rightChar is in charNeedMap (meaning that it is one of the required target characters):
        • Decrement charNeedMap[rightChar].
        • If the need for rightChar becomes exactly 0 (meaning rightChar is now completely covered in the current window), then:
          • Increment fulfilledUniqueCount
          • While window is valid (fulfilledUniqueCount === requiredUniqueCount):
            • Update the best answer: if right - left + 1 < minLength, set minLength and minStart.
            • Try to shrink the window:
              • Let leftChar = s[left]. If leftChar exists in charNeedMap, increment charNeedMap[leftChar].
              • If this changes its count from 0 → 1, a fully satisfied requirement is lost — decrement fulfilledUniqueCount, making the window invalid.
              • Increment left.
    • Result: If minLength === Infinity, no window exists → return "". Otherwise, return s.substring(minStart, minStart + minLength).

Time Complexity

Let n be the length of s and m be the length of t. The algorithm runs in O(n + m) time:

  • Build need map: Initializing charNeedMap from t takes O(m).
  • Single pass over s: The right pointer advances from 0 to n − 1 once, and the left pointer also moves forward at most n times in total. Each pointer update involves constant-time map operations. Therefore, this phases takes O(n).

Therefore: the total time complexity is O(n + m).

Space Complexity

The algorithm uses O(k) auxiliary space, where k is the number of distinct characters in t:

  • Need map: charNeedMap stores at most one entry per unique character in t, resulting in O(k) space usage.
  • Other variables: Scalars such as left, right, minLength, minStart, requiredUniqueCount, and fulfilledUniqueCount use O(1) space.

Since both s and t consist of uppercase and lowercase English letters, the total number of possible unique characters is 52 (A–Z, a–z), which is a fixed constant. Therefore, the overall auxiliary space simplifies to O(1).