Java O(n) solution


  • 0
    T

    Use two pointer: i, j point to the start and end of the window. Move j forward until find a match window that includes all characters in string t. then move i forward to narrow down the window until if(i++), the window will not include all characters. assign this to the final pointer: resultI and resultJ if they are not initialized or larger than current i, j. then i++, and move j to repeat the steps until j reach the end of string s. Use hashMap to indicate how many(value) of the character (key) needed to cover t in s.substring(i, j). negative means still need more of the character, non-negative means had enough, extra number of the character.

    public class Solution {
    public String minWindow(String s, String t) {
        if(s==null || s.length() == 0 || t == null || t.length() == 0) return "";
        
        int sLen = s.length(), tLen = t.length(), count = 0;
        int resultI =-1, resultJ = -1, i =0, j =0;
        char c;
        //create hashMap for target, indicate how many of each characters are needed
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        
        for(int k=0; k<tLen; k++) {
            c = t.charAt(k);
            if(!map.containsKey(c)) map.put(c, -1);
            else map.put(c, map.get(c)-1);
        }
        
        while(j<=sLen) {
            if(count <tLen && j<sLen) {//j++
                c = s.charAt(j);
                if(map.containsKey(c)) {
                    int val = map.get(c)+1;
                    map.put(c,val);
                    if(val <= 0) count++;
                }
                j++;
            } else if(count == tLen) {//i++
                c = s.charAt(i);
                if(map.containsKey(c)) {
                    map.put(c, map.get(c)-1);
                    if(map.get(c) < 0) {//i, j is the potential result
                        count--;
                        if((resultI == -1 && resultJ == -1) || (resultJ-resultI) >(j-i)) {
                            resultI = i;
                            resultJ = j;
                        }
                    }
                }
                i++;
            } else break;//count <tLen && j==sLen
        }
        return (resultI>=0 && resultJ>=0)? s.substring(resultI, resultJ) : "";
    }
    }

Log in to reply
 

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