O(n) Java Solution


  • 0
    P
    public class Solution {
        public String minWindow(String s, String t) {
            if(s == null || t == null || t.length()>s.length() ) return "";
            int[] remaining = new int[128];
            int required = t.length();
            int min = s.length() + 1, start = 0, left = 0;
            for(int i = 0;i<t.length();i++){
                remaining[t.charAt(i)]++;
            }
            int i = 0;
            while(i<=s.length() && start<s.length()){
                if(required>0){
                    if(i == s.length()) break;
                    remaining[s.charAt(i)]--;
                    if(remaining[s.charAt(i)]>=0)required--;
                    i++;
                }else{
                    if(i-start<min){
                        min = i-start;
                        left = start;
                    }
                    remaining[s.charAt(start)]++;
                    if(remaining[s.charAt(start)]>0)required++;
                    start++;
                }
            }
            return min == s.length()+1?"":s.substring(left, left + min);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.