package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/minimum-window-substring/
 */
public class Problem76 {
    public String minWindow(String s, String t) {
        Map<Character, Integer> needed = new HashMap<>();
        for (char c : t.toCharArray()) {
            needed.put(c, needed.getOrDefault(c, 1) + 1);
        }
        Map<Character, Integer> found = new HashMap<>();
        int count = 0;
        int minWindow = Integer.MAX_VALUE;
        int beginIdx = 0;
        int endIdx = 0;
        int begin = 0;
        for (int end = 0; end < s.length(); end++) {
            char endChar = s.charAt(end);
            System.out.println("end: " + end + " --> " + endChar);
            if (!needed.containsKey(endChar)) {
                continue;
            }
            found.put(endChar, found.getOrDefault(endChar, 1) + 1);
//                System.out.println("- incrementing count: " + count);
            count++;
            if (count >= t.length()) {
                char begChar = s.charAt(begin);
//                System.out.println("- end: " + end + " --> " + needed.get(begChar) + " < " + found.get(begChar));
                while (!found.containsKey(begChar) || needed.get(begChar) < found.get(begChar)) {
                    if (!found.containsKey(begChar)) {
                        begChar = s.charAt(begin);
                        begin++;
                    } else {
                        if (needed.get(begChar) < found.get(begChar)) {
                            found.put(begChar, found.get(begChar) - 1);
                            begChar = s.charAt(begin);
                            begin++;
                        }
                    }
                }
                int window = end - begin + 1;
                if (window < minWindow) {
                    beginIdx = begin;
                    endIdx = end;
                    minWindow = window;
                }
            }
        }
        System.out.println(beginIdx + " " + endIdx);
        if (beginIdx == endIdx) {
            return "";
        }
        return s.substring(beginIdx - 1, endIdx + 1);
    }

    public static void main(String[] args) {
        Problem76 prob = new Problem76();
        System.out.println(prob.minWindow("ADOBECODEBANC", "ABC")); // BANC
//        System.out.println(prob.minWindow("ADOBECODEBANC", "ABCX")); //
    }
}

@@ -199,24 +199,26 @@
 String t) %7B%0A
+//
         Map%3C
@@ -255,32 +255,94 @@
 ew HashMap%3C%3E();%0A
+        int size = 128;%0A        int%5B%5D needed = new int%5Bsize%5D;%0A
         for (cha
@@ -362,24 +362,26 @@
 rArray()) %7B%0A
+//
             
@@ -422,24 +422,52 @@
 c, 1) + 1);%0A
+            needed%5Bc%5D += 1;%0A
         %7D%0A  
@@ -456,32 +456,34 @@
 += 1;%0A        %7D%0A
+//
         Map%3CChar
@@ -515,32 +515,69 @@
 ew HashMap%3C%3E();%0A
+        int%5B%5D found = new int%5Bsize%5D;%0A
         int coun
@@ -798,75 +798,8 @@
 d);%0A
-            System.out.println(%22end: %22 + end + %22 --%3E %22 + endChar);%0A
     
@@ -950,22 +950,16 @@
 ) + 1);%0A
-//    
         
@@ -966,62 +966,61 @@
     
-System.out.println(%22- incrementing count: %22 + count);%0A
+if (found.get(endChar) %3C= needed.get(endChar)) %7B%0A    
     
@@ -1032,24 +1032,38 @@
    count++;%0A
+            %7D%0A
             
@@ -1072,17 +1072,17 @@
  (count 
-%3E
+=
 = t.leng
@@ -1141,124 +1141,8 @@
 n);%0A
-//                System.out.println(%22- end: %22 + end + %22 --%3E %22 + needed.get(begChar) + %22 %3C %22 + found.get(begChar));%0A
     
@@ -1951,61 +1951,8 @@
   %7D%0A
-        System.out.println(beginIdx + %22 %22 + endIdx);%0A
     
@@ -2238,18 +2238,16 @@
 // BANC%0A
-//
         

Update problem 76