15ms beats 96% Java O(n) sliding window solution, with comments

• Used an extra map to track chars within window, update this map when an occurred char exceeds its counts, or reset this map when reading an alien char.

``````public class Solution {
public List<Integer> findAnagrams(String s, String p) {
if (s == null || p == null || s.length() == 0 || p.length() == 0 || s.length() < p.length())
return Arrays.asList();
List<Integer> res = new ArrayList<Integer>();
int len = p.length();
int[] letters = new int[26];
for (char c: p.toCharArray())
letters[c - 'a']++;
int[] map = Arrays.copyOf(letters, 26);
int begin = 0, end = 0, count = 0;
while (end < s.length()) {
char cur = s.charAt(end);
if (map[cur - 'a'] > 0) {
map[cur - 'a']--;
count++;
//finished all letters in p
if (len == count) {
map[s.charAt(begin) - 'a']++;
count--;
begin++;
}
end++;
} else {
//reads a char in p, but exceeds
//move begin pointer to the next position of char
if (letters[cur - 'a'] > 0) {
while (s.charAt(begin) != cur) {
map[s.charAt(begin) - 'a']++;
count--;
}
begin++;
end++;
//read a char not in p
} else {
map = Arrays.copyOf(letters, 26);
end++;
begin = end;
count = 0;
}
}
}
return res;
}
}
``````

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