@@ -0,0 +1,1010 @@
+package advanced.scan.window.lc438_findallanagramsinastring;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.%0A * Strings consists of lowercase English letters only.%0A */%0Apublic class Solution %7B%0A%0A    // O(N) time. Window approach.%0A    public List%3CInteger%3E findAnagrams(String s, String p) %7B%0A        int m = s.length(), n = p.length();%0A        int%5B%5D pc = new int%5B256%5D, sc = new int%5B256%5D;%0A        for (int i = 0; i %3C n; i++) pc%5Bp.charAt(i)%5D++;%0A%0A        List%3CInteger%3E ret = new ArrayList%3C%3E();%0A        for (int r = 0, l = r - n, diff = n; r %3C= m; r++, l++) %7B // left, right of window and diff between S and P%0A            if (diff == 0) ret.add(l);%0A            if (r %3C m && ++sc%5Bs.charAt(r)%5D %3C= pc%5Bs.charAt(r)%5D) diff--; // found valid char, decrement diff%0A            if (l %3E= 0 && --sc%5Bs.charAt(l)%5D %3C pc%5Bs.charAt(l)%5D) diff++; // valid char is outside window, increment diff%0A        %7D%0A        return ret;%0A    %7D%0A%0A%7D%0A

find all anagrams in a string