Given a string S and a string T, find the minimum window in S which will contain all the characters in T in linear time complexity. Note that when the count of a character C in T is N, then the count of C in minimum window in S should be at least N.
Example :
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC"
Note:
If there is no such window in S that covers all characters in T, return the empty string ''.
If there are multiple such windows, return the first occurring minimum window ( with minimum start index ).
Method:
Sliding window + hash map
Solution:
Time: O(n) Space: O(n)
public class Solution { public String minWindow(String A, String B) { Map<Character, Integer> map = new HashMap<>(); for (char c : B.toCharArray()) { if (map.containsKey(c)) { map.put(c, map.get(c) + 1); } else { map.put(c, 1); } } int count = map.size(); int left = 0; int right = 0; int minLeft = 0; int minRight = Integer.MAX_VALUE; while (right < A.length()) { char c = A.charAt(right);
if (map.containsKey(c)) { if (map.get(c) == 1) { count --; while (count == 0) { if (minRight - minLeft > right - left) { minLeft = left; minRight = right; } char old = A.charAt(left++); if (map.containsKey(old)) { map.put(old, map.get(old) + 1); if (map.get(old) >= 1) { count ++; } } while (left < A.length() && !map.containsKey(A.charAt(left))) { left ++; } } } map.put(c, map.get(c) - 1); } right ++; } return minRight == Integer.MAX_VALUE ? "" : A.substring(minLeft, minRight + 1); } }
class Solution { public String minWindow(String s, String t) { Map<Character, Integer> map = new HashMap<>(); for (char c : t.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } int count = map.size(); int left = 0; int right = 0; int minLeft = 0; int minRight = s.length(); while (right < s.length()) { char c = s.charAt(right); if (map.containsKey(c)) { map.put(c, map.get(c) - 1); if (map.get(c) == 0) { count --; } while (count == 0 && left <= right) { if (right - left < minRight - minLeft) { minLeft = left; minRight = right; } char leftChar = s.charAt(left); if (map.containsKey(leftChar)) { map.put(leftChar, map.get(leftChar) + 1); if (map.get(leftChar) == 1) { count ++; } } left ++; } } right ++; } if (minRight - minLeft == s.length()) return ""; return s.substring(minLeft, minRight + 1); } }