package com.fishercoder.solutions;

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

/**438. Find All Anagrams in a String
 * Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
 Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

 The order of output does not matter.

 Example 1:
 Input:
 s: "cbaebabacd" p: "abc"
 Output:
 [0, 6]

 Explanation:
 The substring with start index = 0 is "cba", which is an anagram of "abc".
 The substring with start index = 6 is "bac", which is an anagram of "abc".

 Example 2:
 Input:
 s: "abab" p: "ab"
 Output:
 [0, 1, 2]

 Explanation:
 The substring with start index = 0 is "ab", which is an anagram of "ab".
 The substring with start index = 1 is "ba", which is an anagram of "ab".
 The substring with start index = 2 is "ab", which is an anagram of "ab".*/

public class _438 {
    /**
     * O(m*n) solution, my original and most intuitive one, but kind of brute force.
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList();
        for (int i = 0; i <= s.length() - p.length(); i++) {
            if (isAnagram(s.substring(i, i + p.length()), p)) {
                result.add(i);
            }
        }
        return result;
    }

    private boolean isAnagram(String s, String p) {
        int[] c = new int[26];
        for (int i = 0; i < s.length(); i++) {
            c[s.charAt(i) - 'a']++;
            c[p.charAt(i) - 'a']--;
        }

        for (int i : c) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }


    static class SlidingWindowSolution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> result = new ArrayList();
            int[] hash = new int[26];
            for (char c : p.toCharArray()) {
                hash[c - 'a']++;
            }
            int start = 0;
            int end = 0;
            int count = p.length();
            while (end < s.length()) {
                if (hash[s.charAt(end) - 'a'] > 0) {
                    count--;
                }
                hash[s.charAt(end) - 'a']--;
                end++;

                if (count == 0) {
                    result.add(start);
                }

                if ((end - start) == p.length()) {
                    if (hash[s.charAt(start) - 'a'] >= 0) {
                        count++;
                    }
                    hash[s.charAt(start) - 'a']++;
                    start++;
                }
            }
            return result;
        }
    }

    public static void main(String... args) {
        SlidingWindowSolution test = new SlidingWindowSolution();
        String s = "cbaebabacd";
        String p = "abc";
        test.findAnagrams(s, p);
    }
}

@@ -935,12 +935,56 @@
     
-/**%0A
+public static class Solution1 %7B%0A        /**%0A    
     
@@ -1069,19 +1069,27 @@
 e.%0A     
-*/%0A
+    */%0A    
     publ
@@ -1140,32 +1140,36 @@
 ng p) %7B%0A        
+    
 List%3CInteger%3E re
@@ -1192,32 +1192,36 @@
 List();%0A        
+   
+ 
 for (int i = 0; 
@@ -1265,24 +1265,28 @@
             
+    
 if (isAnagra
@@ -1333,32 +1333,36 @@
                 
+ 
+   
 result.add(i);%0A 
@@ -1364,32 +1364,36 @@
 i);%0A            
+    
 %7D%0A        %7D%0A    
@@ -1382,34 +1382,40 @@
   %7D%0A        
+ 
-%7D%0A
+   %7D%0A  
         
 return resul
@@ -1394,32 +1394,34 @@
     %7D%0A          
+  
 return result;%0A 
@@ -1419,27 +1419,35 @@
 result;%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     private 
@@ -1490,24 +1490,28 @@
 ) %7B%0A        
+   
+ 
 int%5B%5D c = ne
@@ -1513,32 +1513,36 @@
  = new int%5B26%5D;%0A
+    
         for (int
@@ -1584,16 +1584,20 @@
         
+    
 c%5Bs.char
@@ -1624,16 +1624,20 @@
         
+   
+ 
 c%5Bp.char
@@ -1652,32 +1652,36 @@
 'a'%5D--;%0A        
+    
 %7D%0A%0A        for (
@@ -1667,32 +1667,36 @@
      %7D%0A%0A        
+  
+  
 for (int i : c) 
@@ -1693,24 +1693,28 @@
 nt i : c) %7B%0A
+    
             
@@ -1739,24 +1739,28 @@
             
+    
 return false
@@ -1765,32 +1765,36 @@
 se;%0A            
+    
 %7D%0A        %7D%0A    
@@ -1779,32 +1779,36 @@
       %7D%0A        
+ 
+   
 %7D%0A        return
@@ -1797,24 +1797,28 @@
   %7D%0A        
+ 
+   
 return true;
@@ -1818,16 +1818,26 @@
 n true;%0A
+        %7D%0A
     %7D%0A%0A%0A
@@ -1840,16 +1840,23 @@
 %7D%0A%0A%0A    
+public 
 static c
@@ -1865,30 +1865,69 @@
 ss S
-li
+olution2 %7B%0A        /**%0A         * Slin
 ding
+ 
 Window
-Solution %7B
+%0A         */
 %0A   
@@ -2933,37 +2933,24 @@
         
-SlidingWindow
 Solution
  test = 
@@ -2941,16 +2941,17 @@
 Solution
+2
  test = 
@@ -2958,29 +2958,16 @@
 new 
-SlidingWindow
 Solution
 ();%0A
@@ -2962,16 +2962,17 @@
 Solution
+2
 ();%0A    

refactor 438