LeetCode [76] Minimum Window Substring

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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

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

class Solution { public: string minWindow(string s, string t) { int cs[256] = {0}; int ct[256] = {0}; int cnt = 0, start = 0, end = 0, maxLen = INT_MAX, ns = s.size(), nt = t.size(); for(auto c:t) ct[c]++; string ret; while (end<ns) { char c1 = s[end]; if(++cs[c1]<=ct[c1]){//add an effective char to cnt cnt++; while(cnt==nt){ char c0 = s[start]; if(--cs[c0]<ct[c0]){//remove an effective char from cnt cnt--; int len = end-start+1; if(len<maxLen){maxLen = len; ret = s.substr(start, len);} } start++; } } end++; } return ret; } };

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

//Java class Solution { public String minWindow(String s, String t) { int m = s.length(), n = t.length(); int l = 0, r = 0; int[] cntS = new int[256]; int[] cntT = new int[256]; for(char c : t.toCharArray()) cntT[c]++ ; int cnt = 0;//effective length String ret = new String(); while(r < m){ char cr = s.charAt(r); cntS[cr]++; if(cntS[cr] <= cntT[cr]){ cnt++; while(cnt == n){ char cl = s.charAt(l); cntS[cl]--; if(cntS[cl] < cntT[cl]){ cnt--; if(ret.length()==0 || ret.length()>r-l+1) ret = s.substring(l, r+1); } l++; } } r++; } return ret; } }