Problem: Minimum Window Substring
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.
A substring is a contiguous sequence of characters within the string.
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 s and t consist of uppercase and lowercase English letters.
class Solution {
public String minWindow(String s, String t) {
HashMap<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 i = 0;
int j = 0;
int count = map.size();
int minimumI = 0;
int minimumJ = 0;
int minimum = Integer.MAX_VALUE;
while(j < s.length()) {
// Calculations for j
if (map.containsKey(s.charAt(j))) {
map.put(s.charAt(j), map.get(s.charAt(j)) - 1);
if (map.get(s.charAt(j)) == 0) {
count--;
}
}
// Check if count is greater than 0. Count will never be less than 0
if (count > 0) {
j++;
}
// Check if condition meets k
else{
while (count == 0) {
if (minimum > j - i + 1) {
minimum = j - i + 1;
minimumI = i;
// As endIndex of substring is exclusive and if we do +1 in return
// So, if empty return is to be returned then too it will return 1st character of the string.
// So if we find the answer then only we will mark it as j+1.
// If answer is not found by our calculations, then as minimumI and minimumJ are zero only, so it will return empty substring.
minimumJ = j + 1;
}
if(map.containsKey(s.charAt(i))){
map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
if(map.get(s.charAt(i))== 1){
count++;
}
}
i++;
}
j++;
}
}
return s.substring(minimumI,minimumJ);
}
}