# Minimum Window Substring ### Source - leetcode: [Minimum Window Substring | LeetCode OJ](https://leetcode.com/problems/minimum-window-substring/) - lintcode: [(32) Minimum Window Substring](http://www.lintcode.com/en/problem/minimum-window-substring/) ### Problem Given a string source and a string target, find the minimum window in sourcewhich will contain all the characters in target. #### Example source = "**ADOBECODEBANC**" target = "**ABC**" Minimum window is "**BANC**". #### Note If there is no such window in source that covers all characters in target,return the emtpy string "". If there are multiple such windows, you are guaranteed that there will alwaysbe only one unique minimum window in source. #### Challenge Can you do it in time complexity O(n) ? #### Clarification Should the characters in minimum window has the same order in target? - Not necessary. ### 題解 計算目標字符串的字符在給定字符串中出現的最小窗口。由于并不需要在給定字符串中有序出現，故只需要統計出現次數。這是典型的需要借助『哈希表』實現的題。題中字符串中的字符可以假定為 ascii 碼，那么我們使用256個 ascii 碼處理起來較為方便。那么接下來有兩個難點，一就是在于怎么知道給定字符串中某一窗口長度已包含目標字符串中的全部字符（可能重復），二是在包含目標字符串中全部字符后如果再出現目標字符串中的其他字符串時如何處理？ 其中第一個難點我們通過巧用目標字符串的長度來處理，遍歷給定字符串，如果給定字符串中出現的字符次數小于目標字符串，我們就更新總的字符出現次數。第二個難題通過維護窗口起止索引（兩根指針）來處理，在給定字符串中出現目標字符串中的全部字符時向前移動窗口起始處，若窗口長度小于之前的窗口長度則更新最終答案要求的窗口起始索引。 ### Java ~~~ public class Solution { /** * @param source: A string * @param target: A string * @return: A string denote the minimum window * Return "" if there is no such a string */ public String minWindow(String source, String target) { if (source == null || target == null) return ""; if (source.length() < target.length()) return ""; final int ASCII_COUNT = 256; int[] targetCount = new int[ASCII_COUNT]; int[] sourceCount = new int[ASCII_COUNT]; for (int i = 0; i < target.length(); i++) { int ch2i = (int)target.charAt(i); targetCount[ch2i]++; } // target string character appeared in source string int winStart = 0, winMinStart = 0, winMin = Integer.MAX_VALUE; int occurence = 0; for (int winEnd = 0; winEnd < source.length(); winEnd++) { // convert character to integer int ch2i = (int)source.charAt(winEnd); sourceCount[ch2i]++; // character occur in both source and target if (targetCount[ch2i] > 0 && targetCount[ch2i] >= sourceCount[ch2i]) { occurence++; } // adjust window size if all the target char occur in source if (occurence == target.length()) { // convert character to integer int ch2i2 = (int)source.charAt(winStart); while (sourceCount[ch2i2] > targetCount[ch2i2]) { sourceCount[ch2i2]--; winStart++; ch2i2 = (int)source.charAt(winStart); } // update winMinStart if (winMin > winEnd - winStart + 1) { winMin = winEnd - winStart + 1; winMinStart = winStart; } } } if (winMin == Integer.MAX_VALUE) { return ""; } else { return source.substring(winMinStart, winMinStart + winMin); } } } ~~~ ### 源碼分析 整個程序最為核心的即為題解中所提出的兩大難點，窗口移動的方法使用貪心實現，在窗口長度變小時需要記錄起始索引。 ### 復雜度分析 遍歷給定字符串一次，外加更新窗口時可能需要遍歷給定字符串一次，時間復雜度為 O(n)O(n)O(n), 使用了幾個額外變量，空間復雜度 O(1)O(1)O(1). ### Reference - [水中的魚: [LeetCode] Minimum Window Substring 解題報告](http://fisherlei.blogspot.com/2012/12/leetcode-minimum-window-substring.html)