Java 6ms Easy to Understand with Explanations


  • 0
    C

    There are two peaks in the runtime distribution chart. To get to the first peek, we need to use arrays as the char maps instead of HashMaps. The idea is to use two pointers "left" and "right", to window a substring of the source string, and keep expanding to right and shrinking from left so that the window always contains all the chars in the target string, and is at its minimum size.

    The code is shown below. There are comments at the key steps.

    public class Solution {
        public String minWindow(String s, String t) {
            int[] sMap = new int[256];
            int[] tMap = new int[256];
            
            char[] tArr = t.toCharArray();
            char[] sArr = s.toCharArray();
            
            for (int i = 0; i < t.length(); i++) {
                char c = tArr[i];
                tMap[c] = tMap[c] + 1;
            }
            
            int start = -1, count = 0, minLength = Integer.MAX_VALUE;
            String minStr = "";
            
            int end = 0;
            while(end < s.length()) {
                // keep expanding to right until the current String contains all the chars in target
                while (end < s.length() && count < t.length()) {
                    char c = sArr[end];
                    if (tMap[c] != 0) {
                        sMap[c] = sMap[c] + 1;
                        if (sMap[c] <= tMap[c]) {
                            count++;
                        }
                    }
                    end++;
                }
                
                // if this is the first expansion and there is not enough char in source, return ""
                if (start == -1 && count < t.length()) return "";
                
                // keep shrinking from left until the the current String no longer contains all the chars in target
                while (count == t.length()) {
                    start++;
                    char cs = sArr[start];
                    if (tMap[cs] != 0) {
                        sMap[cs] = sMap[cs] - 1;
                        if (sMap[cs] < tMap[cs]) {
                            count--;
                        }
                    }
                }
                if (end - start < minLength) {  // update the result if the curr string is shorter.
                    minLength = end - start;
                    minStr = s.substring(start, end);
                }
                
            }
            return minStr;
        }
        
    }
    

Log in to reply
 

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