Java Concise solution with some documentation


  • 0
    V
    public class Solution {
        public String minWindow(String s, String t) {
            if (s == null || t == null || s.length() == 0 || t.length() == 0 || t.length() > s.length()) return "";
            
            // I like this idea from others to use just counters instead of using a Hashmap.
            int[] need = new int[256];
            for (char c : t.toCharArray()) need[c]++;
            
            int lo = 0, minLen = Integer.MAX_VALUE, needed = t.length();
            int[] res = new int[2];
            char[] A = s.toCharArray();
            for(int hi = 0; hi < A.length; hi++) {
                if (need[A[hi]] > 0) needed--;
                
                // Dont really worry about going for -ve values, those will be compensated once the lo moves fwd.
                need[A[hi]]--;
                
                while(needed == 0 && lo <= hi) {
                    if (minLen > hi - lo + 1) {
                        res[0] = lo;
                        res[1] = hi + 1;
                        minLen = hi - lo + 1;
                    }
                    
                    need[A[lo]]++;
                    if (need[A[lo]] > 0) needed++;
                    lo++;
                }
            }
            
            return s.substring(res[0], res[1]);
        }
    }
    

Log in to reply
 

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