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

  • 1

    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++){
                int k = i;
                int j = 0;
                while(k<l1 && j<l2){
                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

    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.