Share my easily understood O(n) Java solution, 6ms


  • 0
    F

    Idea: Two pointers + hash

    Instead of using two while loops, we may use an inner while loop that quickly moves j, and an outer for loop that slowly moves i.
    The O(n) running time should not be affected because it is at most two passes but it is easier to understand.

    Also, size and minStart needs to be updated before each update to the pointer i.

    public class Solution {
        public String minWindow(String s, String t) {
            int minStart = 0, minSz = Integer.MAX_VALUE;
            int counter = 0;
            int[] hash = new int[256];
            for (char ch : t.toCharArray()) {
                hash[ch]++;
                counter++;
            }
            
            int i = 0, j = 0;
            for (i = 0; i < s.length(); i++) {
                // quickly moves j
                while (j < s.length() && counter > 0) {
                    if (hash[s.charAt(j)] > 0) counter--;
                    hash[s.charAt(j)]--;
                    j++;
                }
                if (counter == 0 && j - i < minSz) {
                    minSz = j - i;
                    minStart = i;
                }
                // slowly moves i
                hash[s.charAt(i)]++;
                if (hash[s.charAt(i)] > 0) counter++;
            }
            
            return (minSz == Integer.MAX_VALUE) ? "" : s.substring(minStart, minStart + minSz);
        }
    }
    

Log in to reply
 

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