[LintCode] Substring Anagrams
Problem
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 40,000.
The order of output does not matter.
Example
Given s = "cbaebabacd"p = "abc"
return [0, 6]
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".
Solution
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 40,000.
The order of output does not matter.
Example
Given s = "cbaebabacd"p = "abc"
return [0, 6]
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".
Solution
public class Solution {
public List findAnagrams(String s, String p) {
List res = new ArrayList<>();
if (s == null || p == null || s.length() < p.length()) return res;
//since it's all lowercase English letters
int[] sum = new int[26];
for (char ch: p.toCharArray()) {
sum[ch-'a']++;
}
//build a sliding window
int start = 0, end = 0, matched = 0;
while (end < s.length()) {
int index = s.charAt(end) - 'a';
if (sum[index] > 0) {
matched++;
}
sum[index]--;
end++;
//once the number of matched equals to p.length(), add the start index to result
if (matched == p.length()) {
res.add(start);
}
//move the window forward, restore `sum`
if (end-start == p.length()) {
if (sum[s.charAt(start)-'a'] >= 0) {
matched--;
}
sum[s.charAt(start)-'a']++;
start++;
}
}
return res;
}
}