76. Minimum Window Substring

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

 

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

Input: s = "a", t = "a"
Output: "a"

 

Constraints:

• 1 <= s.length, t.length <= 105
• s and t consist of English letters.

My answer: sliding window. Good answer with template.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

class Solution { public String minWindow(String s, String t) { if (s == null || s.length() == 0 || t == null || t.length() == 0 || s.length() < t.length()) { return ""; } Map<Character, Integer> charCount = new HashMap<Character, Integer>(); for (int i = 0 ; i < t.length(); i ++) { char c = t.charAt(i); int count = charCount.getOrDefault(c, 0); count ++; charCount.put(c, count); } int l = 0; int r = 0; //valid is count of valid chars found in window int valid = 0; String minWindowStr = ""; StringBuilder sb = new StringBuilder(); boolean rMoved = true; Map<Character, Integer> currentCharCount = new HashMap<Character, Integer>(); while(r < s.length()) { char c = s.charAt(r); r ++; sb.append(c); int count = currentCharCount.getOrDefault(c, 0); if (charCount.getOrDefault(c, 0) >= (count + 1)) { // only when expected count not reached // not update if already reached expected count valid ++; if (valid == t.length()) { // found substr contains all chars in t if(minWindowStr.length() == 0) { minWindowStr = sb.toString(); } else if (minWindowStr.length() > sb.length()) { minWindowStr = sb.toString(); } } } count ++; currentCharCount.put(c, count); while (valid == t.length()) { if (sb.length() < minWindowStr.length()) { minWindowStr = sb.toString(); } char d = s.charAt(l); sb.deleteCharAt(0); l ++; int dCount = currentCharCount.get(d); dCount --; currentCharCount.put(d, dCount); if (dCount < charCount.getOrDefault(d, 0)) { // deleting one d cause we have 1 less d in sb than t valid --; } } } return minWindowStr; } }