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<>();
        int size = 128;
        int[] needed = new int[size];
        for (char c : t.toCharArray()) {
//            needed.put(c, needed.getOrDefault(c, 1) + 1);
            needed[c] += 1;
        }
//        Map<Character, Integer> found = new HashMap<>();
        int[] found = new int[size];
        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);
            if (!needed.containsKey(endChar)) {
                continue;
            }
            found.put(endChar, found.getOrDefault(endChar, 1) + 1);
            if (found.get(endChar) <= needed.get(endChar)) {
                count++;
            }
            if (count == t.length()) {
                char begChar = s.charAt(begin);
                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;
                }
            }
        }
        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")); //
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -158,68 +158,8 @@
 ) %7B%0A
-//        Map%3CCharacter, Integer%3E needed = new HashMap%3C%3E();%0A
     
@@ -261,68 +261,8 @@
 ) %7B%0A
-//            needed.put(c, needed.getOrDefault(c, 1) + 1);%0A
     
@@ -282,13 +282,10 @@
 d%5Bc%5D
- += 1
+++
 ;%0A  
@@ -296,67 +296,8 @@
   %7D%0A
-//        Map%3CCharacter, Integer%3E found = new HashMap%3C%3E();%0A
     
@@ -583,36 +583,28 @@
 if (
-!
 needed
-.containsKey(
+%5B
 endChar
-)
+%5D == 0
 ) %7B%0A
@@ -664,57 +664,19 @@
 ound
-.put(
+%5B
 endChar
-, found.getOrDefault(endChar, 1) + 1)
+%5D++
 ;%0A  
@@ -694,29 +694,25 @@
 f (found
-.get(
+%5B
 endChar
-)
+%5D
  %3C= need
@@ -717,21 +717,17 @@
 eded
-.get(
+%5B
 endChar
-)
+%5D
 ) %7B%0A
@@ -879,35 +879,27 @@
 le (
-!
 found
-.containsKey(
+%5B
 begChar
-)
+%5D == 0
  %7C%7C 
@@ -904,37 +904,33 @@
 %7C needed
-.get(
+%5B
 begChar
-)
+%5D
  %3C found
 .get(beg
@@ -917,37 +917,33 @@
 har%5D %3C found
-.get(
+%5B
 begChar
-)
+%5D
 ) %7B%0A        
@@ -962,223 +962,85 @@
 if (
-!found.containsKey(begChar)) %7B%0A                        begChar = s.charAt(begin);%0A                        begin++;%0A                    %7D else %7B%0A                        if (needed.get(begChar) %3C found.get(
+needed%5BbegChar%5D %3C found%5BbegChar%5D) %7B%0A                        found%5B
 begChar
-)) %7B
+%5D--;
 %0A   
@@ -1060,68 +1060,10 @@
     
-        found.put(begChar, found.get(begChar) - 1);%0A        
+%7D%0A
     
@@ -1121,32 +1121,24 @@
             
-     
-   
 begin++;%0A   
@@ -1138,56 +1138,8 @@
 ++;%0A
-                        %7D%0A                    %7D%0A
     
@@ -1386,32 +1386,85 @@
     %7D%0A        %7D%0A
+        System.out.println(beginIdx + %22 %22 + endIdx);%0A
         if (begi
@@ -1553,12 +1553,8 @@
 nIdx
- - 1
 , en
@@ -1806,16 +1806,78 @@
 %22)); //%0A
+        System.out.println(prob.minWindow(%22AA%22, %22AA%22)); // AA%0A
     %7D%0A%7D%0A

Update problem 76