Minimum Window Substring

HardSliding Windowminimum-window-substring

Given two strings s and t, 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.

Example 1:

Input: s = "OUZODYXAZV", t = "XYZ" Output: "YXAZ" Explanation: "YXAZ" is the shortest substring containing characters "X", "Y", and "Z" from string t.

Recommended time and space complexity

The optimal solution has O(n) time complexity and O(k) space complexity, where n is the length of string s, and k is the number of unique characters in string t.


Hint 1

Try using the sliding window technique. Start with a minimum window and expand it until you find all necessary characters.


Hint 2

Use two hash tables: one to count characters in string t, another to track the current window.


Hint 3

After finding a valid window, try to shrink it by moving the left boundary to the right while the window remains valid.

This problem tests skills in working with strings and the sliding window technique. It helps develop understanding of algorithm optimization and working with hash tables.
solution.js · saved

Input

"OUZODYXAZV", "XYZ"

Expected Output

yxaz