*Java* not so short but easy to understand and kinda straightforward solution (13ms)


  • 0
    E

    Here, I am assuming the strings are of ASCII code. If not, we can simply replace the counter array with HashMaps, so no big deal.

    Key idea:

    • Store the occurrence of all characters in s and t into two counter arrays
    • Return "" if no cover (based on comparing the above two counter arrays)
    • Scan the s string and use two pointers pointing to the start and end location of the window. To assist the scanning process, use another counter array that stores the occurrence of all characters within that window. Smartly update the two pointers till the end of the scan.

    Code in Java with comments:

    public class Solution {
    private static final int ASCII_COUNT = 256;
    
    public String minWindow(String s, String t) {
        int L_s = s.length(), L_t = t.length();
        
        // store chracters in s into a counter array
        int[] counts_s = new int[ASCII_COUNT];
        for(int i=0; i<L_s; i++) {
            ++counts_s[s.charAt(i)-0];
        }
        
        // store chracters in t into a counter array
        int[] counts_t = new int[ASCII_COUNT];
        for(int i=0; i<L_t; i++) {
            ++counts_t[t.charAt(i)-0];
        }
        
        // check if there is no valid window
        for(int i=0; i<ASCII_COUNT; i++) {
            if(counts_s[i]<counts_t[i]) return "";
        }
        
        int[] countCovered = new int[ASCII_COUNT];
        int startId = -1, endId = -1;
        int min = -1; // min window length
        for(int i=0; i<L_s; i++) {
            char ch = s.charAt(i);
            int id = ch - 0;
            
            // initiate startId of the window if not already initialized
            if(startId==-1 && counts_t[id]!=0) {
                startId = i;
                countCovered[id] = 1;
            }
            else if(startId!=-1) {
                // previous window is A..... and now meets another A at index i and count of A prior to index i is already a cover
                if(countCovered[id]>=counts_t[id] && ch==s.charAt(startId)) {
                    
                    // Move startId to the right till hitting a character that is not a cover
                    while(countCovered[s.charAt(++startId)-0] > counts_t[s.charAt(startId)-0]) {
                        --countCovered[s.charAt(startId)-0]; // update cover counter
                    }
                    
                    // update min and endId if necessary
                    if(i-startId+1 < min) {
                        endId = i;
                        min = endId - startId + 1;
                    }
                }
                // previous windown is A..... and now meets an X where X can be anything
                else { 
                    ++countCovered[id]; // update cover counter
                }
            }
            
            // if previous window is not a cover, check if it is now a cover. isCoveringAll is called only once because min will no longer be -1 afterwards
            if(min==-1 && startId!=-1 && counts_t[id]>0 && isCoveringAll(countCovered, counts_t)) {
                endId = i;
                min = endId - startId + 1;
            }
        }
        
        return s.substring(endId-min+1, endId+1);
    }
    
    private boolean isCoveringAll(int[] countCovered, int[] counts_t) {
        for(int i=0; i<ASCII_COUNT; i++) {
            if(countCovered[i]<counts_t[i]) return false;
        }
        return true;
    }
    }
    

    If you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java


Log in to reply
 

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