Simple sliding window solution in Java [Time: O(S*T), Space: O(1)]


  • 1
    K

    Whenever there is a match between the first character of the String T and the i th character of String S begin searching for the sequence T in S.

    public String minWindow(String S, String T) {
        int l1 = S.length();
        int l2 = T.length();
        int min = Integer.MAX_VALUE;
        int minInd = 0;
        for(int i=0;i<l1-l2+1;i++){
            if(S.charAt(i)==T.charAt(0)){
                int k = i;
                int j = 0;
                while(k<l1 && j<l2){
                    if(S.charAt(k++)==T.charAt(j))
                        j++;
                }
                
                if(j==l2 && k-i<min){
                    min = Math.min(min, k-i);
                    minInd = i;
                }
            }
        }
        return min==Integer.MAX_VALUE?"":S.substring(minInd, minInd+min);
    }

  • 0
    B

    It is very clear that the k in your while(k<l1 && j<l2) can be advanced at most S - i times. For maximum, k = S, when i=0. For minimum, k = T, when i = S-T. Thus your algorithm runs in approximately 1/2*(S+T)*(S-T) time. When T<<S, it is just O(S^2), and by no means is O(S*T).


Log in to reply
 

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