Leetcode - Minimum Window Substring

Question

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

This is asliding_window question.

Idea

• Use a sliding window approach (L & R)
• Keep two hash maps (have (s) and need (t), our success condition is if each key in want ≤ their corresponding keys in need)
  • Instead of checking equality in each key each time… We can hold two integer values which represent the state of their respective hash maps. As we iterate throughout s, we check the hash map equality of the character we are currently on (s[R]) (must be exactly equal now) and update our state accordingly.
    • If we have exact quality increment have
• Since we want to find the minimum substring loop while states are exactly equal
  • Once we have states that are exactly equal update the result min(res, R - L + 1)
  • decrement s[L] from have
  • If have[s[L]] < need[s[L]] then decrement out have state
  • Slide L
• Return res

Solution