O(N) JAVA Sliding Window solution with explanation


  • 7

    Sliding Window Solution:

    1) Spread the right pointer until it satisfies the requirement  
    2) Shrink the left pointer to get the minimum range 
    3) Keep the above steps.
    

    Time complexity = O(2n) = O(n)

    There're 2 loops: for loop of i, while loop of j. As j only steps forward, never steps backward. So time complexity = O(n) + O(n) = O(2n) = O(n)

    JAVA Code:

    A little trick is using two arrays to count the characters in s and t, instead of HashMap, to avoid TLE.

    boolean sContainsT(int mapS[], int mapT[]) {// Runtime = O(256) = O(1)
        for (int i = 0; i < mapT.length; i++) {// s should cover all characters in t
            if (mapT[i] > mapS[i])
                return false; 
        }           
        return true;
    }
    
    public String minWindow(String s, String t) {   
        int mapS[] = new int[256];// Count characters in s
        int mapT[] = new int[256];// Count characters in t      
        for (char ch : t.toCharArray())
            mapT[ch]++;
    
        String res = "";
        int right = 0, min = Integer.MAX_VALUE;         
        for (int i = 0; i < s.length(); i++) {// Two pointers of the sliding window: i(left), right
            while (right < s.length() && !sContainsT(mapS, mapT)) {// Extend the right pointer of the sliding window
                mapS[s.charAt(right)]++;
                right++;
            }
            if (sContainsT(mapS, mapT) && min > right - i + 1) {
                res = s.substring(i, right);
                min = right - i + 1;
            }
            mapS[s.charAt(i)]--;// Shrink the left pointer from i to i + 1
        }
        return res;
    }

  • 0
    M

    obviously this is not O(N), since for each i you call isCovered(), which takes O(len(T)) time.


  • -5
    Y

    I think you cannot assume that the characters are ascii.


  • 0
    M

    Looks like O(N^2) to me. In the worst case, for every i, you could go to the end of string s.


Log in to reply
 

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