package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/substring-with-concatenation-of-all-words/
 */
public class Problem30 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        int wordSize = words[0].length();
        int totalSize = wordSize * words.length;
        if (totalSize > s.length()) {
            return result;
        }
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (!map.containsKey(word)) {
                map.put(word, 1);
            } else {
                map.put(word, map.get(word) + 1);
            }
        }
        List<String> removedWords = new ArrayList<>();
        int i = 0;
        while (i + totalSize <= s.length()) {
            int j = i;
            for (; j + wordSize <= s.length(); j++) {
                String sub = s.substring(j, j + wordSize);
                if (!map.containsKey(sub)) {
                    break;
                } else {
                    int newCount = map.get(sub) - 1;
                    if (newCount == 0) {
                        map.remove(sub);
                    } else {
                        map.put(sub, newCount);
                    }
                    removedWords.add(sub);
                }
                j += wordSize - 1;
            }
            if (map.isEmpty()) {
                result.add(i);
            }
            for (String word : removedWords) {
                if (map.containsKey(word)) {
                    map.put(word, map.get(word) + 1);
                } else {
                    map.put(word, 1);
                }
            }
            removedWords.clear();
            i++;
        }
        return result;
    }

    public static void main(String[] args) {
        Problem30 prob = new Problem30();
        System.out.println(prob.findSubstring("barfoothefoobarman", new String[]{"foo", "bar"})); // [0, 9]
        System.out.println(prob.findSubstring("foobarthefoobarman", new String[]{"foo", "bar"})); // [0, 9]
        System.out.println(prob.findSubstring("barbazthebarbarfoobaz", new String[]{"foo", "bar"})); // [12]
        System.out.println(prob.findSubstring("barbazbebarbarfoobaz", new String[]{"foo", "bar"})); // [11]
        System.out.println(prob.findSubstring("barbazthebarbarfoobaz", new String[]{"foo", "bar", "baz"})); // [12]
        System.out.println(prob.findSubstring("barbazthebarbarfoobaz", new String[]{"foo", "bar", "bar"})); // [9]
        System.out.println(prob.findSubstring("barfoofoobarthefoobarman", new String[]{"bar", "foo", "the"})); // [6, 9, 12]
        System.out.println(prob.findSubstring("aaaaaaaa", new String[]{"aa", "aa", "aa"})); // [0, 1, 2]
        System.out.println(prob.findSubstring("a", new String[]{"a"})); // [0]
    }
}

@@ -767,63 +767,8 @@
   %7D%0A
-        List%3CString%3E removedWords = new ArrayList%3C%3E();%0A
     
@@ -851,16 +851,76 @@
  j = i;%0A
+            Map%3CString, Integer%3E copy = new HashMap%3C%3E(map);%0A
         
@@ -1037,35 +1037,36 @@
            if (!
-map
+copy
 .containsKey(sub
@@ -1157,19 +1157,20 @@
 Count = 
-map
+copy
 .get(sub
@@ -1241,19 +1241,20 @@
         
-map
+copy
 .remove(
@@ -1308,27 +1308,28 @@
             
-map
+copy
 .put(sub, ne
@@ -1363,51 +1363,8 @@
   %7D%0A
-                    removedWords.add(sub);%0A
     
@@ -1442,19 +1442,20 @@
     if (
-map
+copy
 .isEmpty
@@ -1521,1387 +1521,45 @@
     
-for (String word : removedWords) %7B%0A                if (map.containsKey(word)) %7B%0A                    map.put(word, map.get(word) + 1);%0A                %7D else %7B%0A                    map.put(word, 1);%0A                %7D%0A            %7D%0A            removedWords.clear();%0A            i++;%0A        %7D%0A        return result;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem30 prob = new Problem30();%0A        System.out.println(prob.findSubstring(%22barfoothefoobarman%22, new String%5B%5D%7B%22foo%22, %22bar%22%7D)); // %5B0, 9%5D%0A        System.out.println(prob.findSubstring(%22foobarthefoobarman%22, new String%5B%5D%7B%22foo%22, %22bar%22%7D)); // %5B0, 9%5D%0A        System.out.println(prob.findSubstring(%22barbazthebarbarfoobaz%22, new String%5B%5D%7B%22foo%22, %22bar%22%7D)); // %5B12%5D%0A        System.out.println(prob.findSubstring(%22barbazbebarbarfoobaz%22, new String%5B%5D%7B%22foo%22, %22bar%22%7D)); // %5B11%5D%0A        System.out.println(prob.findSubstring(%22barbazthebarbarfoobaz%22, new String%5B%5D%7B%22foo%22, %22bar%22, %22baz%22%7D)); // %5B12%5D%0A        System.out.println(prob.findSubstring(%22barbazthebarbarfoobaz%22, new String%5B%5D%7B%22foo%22, %22bar%22, %22bar%22%7D)); // %5B9%5D%0A        System.out.println(prob.findSubstring(%22barfoofoobarthefoobarman%22, new String%5B%5D%7B%22bar%22, %22foo%22, %22the%22%7D)); // %5B6, 9, 12%5D%0A        System.out.println(prob.findSubstring(%22aaaaaaaa%22, new String%5B%5D%7B%22aa%22, %22aa%22, %22aa%22%7D)); // %5B0, 1, 2%5D%0A        System.out.println(prob.findSubstring(%22a%22, new String%5B%5D%7B%22a%22%7D)); // %5B0%5D
+i++;%0A        %7D%0A        return result;
 %0A   

Solve problem 30