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.
Follow up: Could you find an algorithm that runs in O(m + n) time?
class Solution {
public String minWindow(String s, String t) {
if(s == null || s.length() < t.length() || s.length() == 0){
return "";
}
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(char c : t.toCharArray()){
if(map.containsKey(c)){
map.put(c,map.get(c)+1);
}else{
map.put(c,1);
}
}
int left = 0;
int minLeft = 0;
int minLen = s.length()+1;
int count = 0;
for(int right = 0; right < s.length(); right++){
if(map.containsKey(s.charAt(right))){
map.put(s.charAt(right),map.get(s.charAt(right))-1);
if(map.get(s.charAt(right)) >= 0){
count ++;
}
while(count == t.length()){
if(right-left+1 < minLen){
minLeft = left;
minLen = right-left+1;
}
if(map.containsKey(s.charAt(left))){
map.put(s.charAt(left),map.get(s.charAt(left))+1);
if(map.get(s.charAt(left)) > 0){
count --;
}
}
left ++ ;
}
}
}
if(minLen>s.length())
{
return "";
}
return s.substring(minLeft,minLeft+minLen);
}
}