# Java 13ms solution, fast than below shortest solution by sliding window, Why?

• `Update:`
after release my solution, I saw the Shortest/Concise JAVA O(n) Sliding Window Solution, it is very great. But my complexity code looks like more fast. so still share just for fun.

To len (P) as the window, traverse the s from left to right.
We use the `pre` to show whether the last traversal was successful in finding the Anagrams. when `pre = true`, there will be three kinds of situations:
1、s[start -1] == s[end] direct add
2、the new char of s[end] is not in p
3、the new char of s[end] is in p, but s[end] is not the s[start - 1]

by using this method, we can save some unnecessary calculations.

``````public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (p.length() > s.length()) return res;

int[] base = new int[26];
int len = p.length();
for (int i = 0; i < len; i++) {
base[p.charAt(i) - 'a']++;
}

int[] count = new int[26];
boolean pre = false;  //is last combination is a Anagrams
int start = 0;  //start of len(p) window in s
int end = start + len - 1;  //end of len(p) window in s
int loop = len;  //the len that we will loop to calculate the sum in every window.

for (; start <= s.length() - len; start++, end++) {
if (!pre) {
for (int i = loop; i > 0; i--) {
count[s.charAt(end - i + 1) - 'a']++;
}

int i = 0;
while (i < base.length) {
if (base[i] != count[i]) break;
i++;
}
if (i == base.length) {
pre = true;
} else {
//                    Arrays.fill(count, 0);  //optimization
count[s.charAt(start) - 'a']--;
loop = 1;
}
} else {
char last = s.charAt(end);
//Three kinds of situations
//1、s[start -1] == s[end] direct add
//2、the new char of s[end] is not in p
//3、the new char of s[end] is in p, but s[end] is not the s[start - 1]
if (last == s.charAt(start - 1)) res.add(start);
else if (base[last - 'a'] == 0) {
Arrays.fill(count, 0);
loop = len;
start = end;
end = start + len - 1;
pre = false;
} else {
int i = start;
count[s.charAt(i - 1) - 'a']--;
for (; i < end; i++) {
char cur = s.charAt(i);
if (cur != last) count[cur - 'a']--;
else break;
}
//space char is i - start + 1, Backward extension
loop = i - start + 1;
//i + 1 ==> start
start = i;
end = start + len - 1;
pre = false;
}
}

}
return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.