package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/substring-with-concatenation-of-all-words/
 */
public class Problem30 {
    public List<Integer> findSubstring(String s, String[] words) {
        // TODO
        return new ArrayList<>();
    }

    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]
    }
}

@@ -57,20 +57,68 @@
 va.util.
-List
+HashMap;%0Aimport java.util.List;%0Aimport java.util.Map
 ;%0A%0A/**%0A 
@@ -300,48 +300,1495 @@
     
-// TODO%0A        return new ArrayList%3C%3E()
+Map%3CString, Integer%3E map = new HashMap%3C%3E();%0A        for (String word : words) %7B%0A            if (!map.containsKey(word)) %7B%0A                map.put(word, 1);%0A            %7D else %7B%0A                map.put(word, map.get(word) + 1);%0A            %7D%0A        %7D%0A        List%3CInteger%3E result = new ArrayList%3C%3E();%0A        int wordSize = words%5B0%5D.length();%0A        List%3CString%3E removedWords = new ArrayList%3C%3E();%0A        int i = 0;%0A        while (i %3C s.length()) %7B%0A            int j = i;%0A            for (; j + wordSize %3C= s.length(); j++) %7B%0A                String sub = s.substring(j, j + wordSize);%0A                if (!map.containsKey(sub)) %7B%0A                    break;%0A                %7D else %7B%0A                    int newCount = map.get(sub) - 1;%0A                    if (newCount == 0) %7B%0A                        map.remove(sub);%0A                    %7D else %7B%0A                        map.put(sub, newCount);%0A                    %7D%0A                    removedWords.add(sub);%0A                %7D%0A                j += wordSize - 1;%0A            %7D%0A            if (map.isEmpty()) %7B%0A                result.add(i);%0A                i = j + wordSize;%0A            %7D else %7B%0A                i++;%0A            %7D%0A            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        %7D%0A        return result
 ;%0A  
@@ -1875,24 +1875,26 @@
 roblem30();%0A
+//
         Syst
@@ -1981,32 +1981,34 @@
 %22%7D)); // %5B0, 9%5D%0A
+//
         System.o
@@ -2099,16 +2099,18 @@
  %5B0, 9%5D%0A
+//
         
@@ -2210,16 +2210,486 @@
 // %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
     %7D%0A%7D%0A

Update problem 30