Neat Java O(N) solution.


  • 0
    A

    public class Solution {
    public String minWindow(String s, String t) {

        if(s.length() < t.length()) {
            return "";
        }
        
        int[] counter = new int[256];
        for(int i = 0;i < t.length();i++) {
            counter[t.charAt(i)]++;
        }
        int minLen = Integer.MAX_VALUE;
        String minStr = "";
        int j = 0;
        for(int i = 0;i < s.length();i++) {
            while(j < s.length()) {
                if(!isValid(counter)) {
                    counter[s.charAt(j)]--;
                    j++;
                } else {
                    break;
                }
            }
            if(isValid(counter) && j - i + 1 < minLen) {
                minLen = j - i + 1;
                minStr = s.substring(i, j);
            }
            counter[s.charAt(i)]++;
        }
        return minStr;
        
    }
    
    private boolean isValid(int[] counter) {
        for(int i = 0;i < counter.length;i++) {
            if(counter[i] > 0) {
                return false;
            }
        }
        return true;
    }
    

    }


Log in to reply
 

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