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) {
        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<Integer> result = new ArrayList<>();
        int wordSize = words[0].length();
        List<String> removedWords = new ArrayList<>();
        int i = 0;
        while (i < 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);
                i = i + wordSize;
            } else {
                i++;
            }
            for (String word : removedWords) {
                if (map.containsKey(word)) {
                    map.put(word, map.get(word) + 1);
                } else {
                    map.put(word, 1);
                }
            }
            removedWords.clear();
        }
        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]
    }
}

@@ -280,32 +280,248 @@
 ring%5B%5D words) %7B%0A
+        List%3CInteger%3E result = new ArrayList%3C%3E();%0A        int wordSize = words%5B0%5D.length();%0A        int totalSize = wordSize * words.length;%0A        if (totalSize %3E s.length()) %7B%0A            return result;%0A        %7D%0A
         Map%3CStri
@@ -552,24 +552,24 @@
 ashMap%3C%3E();%0A
-
         for 
@@ -767,100 +767,8 @@
   %7D%0A
-        List%3CInteger%3E result = new ArrayList%3C%3E();%0A        int wordSize = words%5B0%5D.length();%0A
     
@@ -854,17 +854,30 @@
 hile (i 
-%3C
++ totalSize %3C=
  s.lengt
@@ -1528,84 +1528,8 @@
 i);%0A
-                i = i + wordSize;%0A            %7D else %7B%0A                i++;%0A
     
@@ -1809,24 +1809,41 @@
 ds.clear();%0A
+            i++;%0A
         %7D%0A  
@@ -2621,16 +2621,16 @@
  // %5B9%5D%0A
-
         
@@ -2742,20 +2742,204 @@
  %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%0A
     %7D%0A%7D%0A

Update problem 30