Minimum Window Substring
Problem Description
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.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Example 3:
Input: s = "a", t = "aa"Output: ""Explanation: Both 'a's from t must be included in the window.Since the largest window of s only has one 'a', return empty string.
Constraints:
- m == s.length
- n == t.length
- 1 <= m, n <= 105
sandtconsist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
Solve it on LeetCode
Approaches
1. Brute Force
The most straightforward solution is to generate all possible substrings of s, and check if they contain all characters of t. However, this will be highly inefficient due to the large number of potential substrings, especially for long input strings.
Intuition:
- Generate all possible substrings of
s. - For each substring, count its characters and check if they match those in
t. - Track the minimum-length substring that contains all characters of
t.
Code:
- Time Complexity: O(n^3) due to the checking of all substrings and counting of characters.
- Space Complexity: O(1), no additional data structures are used aside from fixed-size arrays for counting characters.
2. Sliding Window using HashMap
The sliding window technique optimizes the process of finding the minimum window by maintaining two pointers to represent a window and expanding or shrinking it as needed.
Intuition:
- Use two pointers: one to expand the window (
right), and one to contract it (left). - Use a HashMap to keep track of characters' frequencies in the current window.
- When the window contains all characters of
t, try to shrink it by moving theleftpointer to minimize the window size. - Record the smallest window found.
Code:
- Time Complexity: O(n + m), where
nis the length ofs, andmis the length oft. This is because each character is processed at most twice (once whenrighttraversess, and once whenleftincrements). - Space Complexity: O(m + k), where
mis the size of thetFreqHashMap that stores character frequencies oft, andkis the maximum number of unique characters ins.