Easy to understand java code using List and matching array.


  • 0
    L
    public String minWindow(String s, String t) {
            if (t == null || t.length() == 0 || s== null || s.length() == 0) return "";
            int[][] match = new int[256][2];
            int count = 0;
            for (int i = 0; i < t.length(); i++) {
                int c = (int) t.charAt(i);
                match[c][0]++;
                count++;
            }
            
            List<Integer> elements = new ArrayList<Integer>();        
            int start = 0, end = Integer.MAX_VALUE;
            
            for (int i = 0; i < s.length(); i++) {
                int c = (int) s.charAt(i);
                if (match[c][0] > 0) { //needed char.
                    elements.add(i);                
                    if (match[c][0] > match[c][1]) count--;
                    match[c][1]++;
                    
                    while (!elements.isEmpty()) {
                        int sc = (int) s.charAt(elements.get(0));
                        if (match[sc][0] < match[sc][1]) { //try to remove from the tail.
                            elements.remove(0);
                            match[sc][1]--;
                        } else break;   
                    }
                    
                    if (match[c][0] == match[c][1] && count == 0) {
                        int sc = elements.get(0);
                        if (i - sc < end - start) {
                            start = sc;
                            end = i;
                        }
                    }
                }
            }
            
            if (end < s.length()) return s.substring(start, end + 1);
            else  return "";
        }
    

Log in to reply
 

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