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).
Example
S = "ADOBECODEBANC", T = "ABC", Minimum window is "BANC".
JavaScript Code
function minWindow(s, t) { if(t.length > s.length) return ""; var result = ""; //character counter for t var target = {}; for(var i=0; i<t.length; i++){ var c = t.charAt(i); if(target[c]!=null){ target[c] = target[c]+1; }else{ target[c] = 1; } } // character counter for s var map = {}; var left = 0; var minLen = s.length+1; var count = 0; // the total of mapped characters for(var i=0; i<s.length; i++){ var c = s.charAt(i); if(target[c]!=null){ if(map[c]!=null){ if(map[c]<target[c]){ count++; } map[c] = map[c]+1; }else{ map[c] = 1; count++; } } if(count == t.length){ var sc = s.charAt(left); while ((map[sc]==null) || map[sc] > target[sc]) { if (map[sc]!=null && map[sc] > target[sc]) map[sc] = map[sc] - 1; left++; sc = s.charAt(left); } if (i - left + 1 < minLen) { result = s.substring(left, i + 1); minLen = i - left + 1; } } } return result; } console.log(minWindow('ADOBECODEBANC', 'ABC'));
0 comments:
Post a Comment