Problem:
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For 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 emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
Analysis:
The idea behind this problem is very very important!!! It's an important pattern to slove a cluster problem over string : Permutataion, Substring, Concatenation. Basic idea: maintain a slide window to circle out the target String. It usually follow following routines. 1. Prepare two hashmaps, one is to record the characters appear target String, the other one is to record the characters appear in our slide window. 2. To maintain the slide window, we need to adjust the left side and right side of the slide window. Since this problem does not care to include extra characters into the window, as long as the subset of the window meet the condidation. We don't need to adjust on right side(which makes problem much easier). Take a look at this problem: https://leetcode.com/problems/substring-with-concatenation-of-all-words/ Which requires adjust right side (word in the window must the exactly same)!!! 3. We should also maintain a count variable for counting the useful character in the window. It's very important for us to know when to start a new window. Initially, I have came up with the following ugly solution, which includes complex board checking and hard to understand. public class Solution { public String minWindow(String s, String t) { if (s == null || t == null || t.length() > s.length()) return ""; int min_count = Integer.MAX_VALUE; int min_left = 0, min_right = 0; int left = 0, right; int count = 0; HashMap<Character, Integer> to_find = new HashMap<Character, Integer> (); HashMap<Character, Integer> found = new HashMap<Character, Integer> (); for (int i = 0; i < t.length(); i++) { if (to_find.containsKey(t.charAt(i))) { to_find.put(t.charAt(i), to_find.get(t.charAt(i))+1); } else{ to_find.put(t.charAt(i), 1); } } while (left < s.length() && !to_find.containsKey(s.charAt(left)) ) { left++; } for (right = left; right < s.length(); right++) { char temp = s.charAt(right); if (to_find.containsKey(temp)) { if (found.containsKey(temp)) { found.put(temp, found.get(temp)+1); } else{ found.put(temp, 1); } if (found.get(temp) <= to_find.get(temp)) count++; } if (count == t.length()) { if (right - left < min_count) { min_count = right - left; min_left = left; min_right = right; } //ready to skip the element pointed by left pointer found.put(s.charAt(left), found.get(s.charAt(left))-1); left++; count--; while (left < s.length() && !to_find.containsKey(s.charAt(left))) { left++; } } } if (min_count == Integer.MAX_VALUE) { return ""; } return s.substring(min_left, min_right+1); } } My idea for this solution is that: 1. The slide window should always start from the valid character(the character appears in the target string "s"). Thus we have a ugly logic to move left side. This kind of "while loop" could easily exceed the borader and hard to maintain. You need to make the adjustment: a. when you start the search. b. when you adjust the left side of slide window. ----------------------------------------------------------------------------------------------- while (left < s.length() && !to_find.containsKey(s.charAt(left))) { left++; } And we need to start from for (right = left; right < s.length(); right++) { This condidation makes the code quite ugly. 2. Since the window's left side include the valid character in target string "s", when "count == t.length()", all character in the slide window consist the minimum substring. However, it fails for the following case: Input: "bba", "ab" Output: "bba" Expected: "ba" *************** Lessson: Even a character is valid, it is still could be useless for the current window. The useless character could happens for following situation <Even the character appears in the target String s> s:aabc t:abc <The character not appear in the target String s> s:dabc t:abc A very useful/tricky way to solve this problem is we don't care about the character we have include into the window, when we move the right side. We based on the count value to decide whether the current window could have a substring. Once the count reach "count == t.length()", it must a solution. Then we continue to adjust window's left side to get other solutions, as long as the count meets "count == t.length()". Count is the only criteria we used to decide if a string is solution. if (right - left + 1 < min_len) { min_len = right - left + 1; min_left = left; min_right = right; } if (to_find.containsKey(s.charAt(left))) { found.put(s.charAt(left), found.get(s.charAt(left))-1); if (found.get(s.charAt(left)) < to_find.get(s.charAt(left))) count--; } //as long as count is still valid, we could move left side. left++; key: 1. HashMap for recording numbers. (as long as a charcter is valid, we record it into Hashmap) 2. Count for checking if a String meet the condition. if (to_find.containsKey(temp)) { if (found.containsKey(temp)) { //Must enter hashmap, but we based on quantity realtionship to check if it's useful. found.put(temp, found.get(temp)+1); } else{ found.put(temp, 1); } //means the added character is useful for reaching target if (found.get(temp) <= to_find.get(temp)) count++; } if (to_find.containsKey(s.charAt(left))) { found.put(s.charAt(left), found.get(s.charAt(left))-1); if (found.get(s.charAt(left)) < to_find.get(s.charAt(left))) count--; } How to use? How to check? The respective's resonsiblity must be very clear.
Solution:
public class Solution { public String minWindow(String s, String t) { if (s == null || t == null || t.length() > s.length()) return ""; int min_len = Integer.MAX_VALUE; int min_left = 0, min_right = 0; int left = 0; int count = 0; HashMap<Character, Integer> to_find = new HashMap<Character, Integer> (); HashMap<Character, Integer> found = new HashMap<Character, Integer> (); for (int i = 0; i < t.length(); i++) { if (to_find.containsKey(t.charAt(i))) { to_find.put(t.charAt(i), to_find.get(t.charAt(i))+1); } else{ to_find.put(t.charAt(i), 1); } } for (int right = 0; right < s.length(); right++) { char temp = s.charAt(right); if (to_find.containsKey(temp)) { if (found.containsKey(temp)) { found.put(temp, found.get(temp)+1); } else{ found.put(temp, 1); } //the new add character is useful for eaching target t if (found.get(temp) <= to_find.get(temp)) count++; } //at least meet the condition. while (count == t.length()) { if (right - left + 1 < min_len) { min_len = right - left + 1; min_left = left; min_right = right; } if (to_find.containsKey(s.charAt(left))) { found.put(s.charAt(left), found.get(s.charAt(left))-1); if (found.get(s.charAt(left)) < to_find.get(s.charAt(left))) count--; } left++; } } if (min_len == Integer.MAX_VALUE) { return ""; } return s.substring(min_left, min_right+1); } }