Minimum Window Substring Leetcode Solution
Minimum Window Substring Leetcode Problem :
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.
Minimum Window Substring Leetcode Problem Solution :
Constraints :
- m == s.length
- n == t.length
- 1 <= m, n <= 105
- s and t consist of uppercase and lowercase English letters.
Example 1:
- 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.
Example 2:
- Input: s = “a”, t = “a”
- Output: “a”
- Explanation: The entire string s is the minimum window.
Idea to solve:
The problem asks to find the minimum window in s that contains all the characters of t. One way to approach this problem is to use a sliding window technique. We can maintain a window that starts from the beginning of s and moves forward until it contains all the characters of t. Once we have such a window, we can try to shrink it by moving the window’s start pointer forward while still keeping all the characters of t in the window. This will give us the minimum window.
Approach:
- Check if s is shorter than t. If it is, there is no possible solution, and we return an empty string.
- Create a frequency map of characters in t.
- Initialize count, start, min_length, and min_start to 0.
- Traverse the string s using the end pointer.
- If the current character in s is present in the frequency map, increment the count.
- Decrement the frequency of the current character in the frequency map.
- If the count equals the length of t, it means we have found a window that contains all characters of t. Now we try to shrink the window by moving the start pointer forward until the window still contains all the characters of t.
- If the length of the current window is smaller than the minimum length so far, update the minimum length and the minimum start.
- Increment the frequency of the character at the start pointer and decrement the count.
- Return the minimum window or an empty string if no window exists.
Complexity:
Time complexity: O(N), where N is the length of the string s.
We traverse the string s once.Space complexity: O(M), where M is the length of the string t.
We create a frequency map of characters in t.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
string minWindow(string s, string t) {
if(s.size() < t.size()){
return "";
}
unordered_map< char,int> map;
for(int i=0;i < t.size();i++){
map[t[i]]++;
}
int count=0,start=0,min_length = INT_MAX, min_start = 0;
for(int end=0; end< s.size(); end++){
if(map[s[end]]>0){
count++;
}
map[s[end]]--;
if(count == t.length()) {
while(start < end && map[s[start]] < 0){
map[s[start]]++, start++;
}
if(min_length > end-start){
min_length = end-(min_start=start)+1;
}
map[s[start++]]++;
count--;
}
}
return min_length == INT_MAX ? "" : s.substr(min_start, min_length);
}
};
class Solution {
public String minWindow(String s, String t) {
if(s.length() < t.length()){
return "";
}
Map< Character,Integer> map = new HashMap<>();
for(int i=0;i < t.length();i++){
map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
}
int count=0,start=0,min_length = Integer.MAX_VALUE, min_start = 0;
for(int end=0; end < s.length(); end++){
if(map.containsKey(s.charAt(end))){
if(map.get(s.charAt(end))>0){
count++;
}
map.put(s.charAt(end), map.get(s.charAt(end))-1);
}
if(count == t.length()) {
while(start < end && (!map.containsKey(s.charAt(start)) || map.get(s.charAt(start)) < 0)){
if(map.containsKey(s.charAt(start))){
map.put(s.charAt(start), map.get(s.charAt(start))+1);
}
start++;
}
if(min_length > end-start+1){
min_length = end-(min_start=start)+1;
}
if(map.containsKey(s.charAt(start))){
map.put(s.charAt(start), map.get(s.charAt(start))+1);
}
count--;
start++;
}
}
return min_length == Integer.MAX_VALUE ? "" : s.substring(min_start, min_start+min_length);
}
}class Solution(object):
def minWindow(self, s, t):
if len(s) < len(t):
return ""
map = {}
for char in t:
if char in map:
map[char] += 1
else:
map[char] = 1
count = 0
start = 0
min_length = float("inf")
min_start = 0
for end in range(len(s)):
if s[end] in map:
map[s[end]] -= 1
if map[s[end]] >= 0:
count += 1
while count == len(t):
if min_length > end - start + 1:
min_length = end - start + 1
min_start = start
if s[start] in map:
map[s[start]] += 1
if map[s[start]] > 0:
count -= 1
start += 1
return "" if min_length == float("inf") else s[min_start:min_start+min_length]
Login/Signup to comment