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 Solution {
public List<int> FindAnagrams(string s, string p) {
List<int> list = new List<int>();
if (string.IsNullOrWhiteSpace(s) || s.Length < p.Length)
return list;
int sum = 0;
int[] pArray = new int[26];
foreach (char c in p){
sum = sum + (c - 'a');
++pArray[c - 'a'];
}
int sum1 = 0;
int startIndex = 0;
for (int endIndex = 0; endIndex < s.Length; endIndex++){
if (pArray[s[endIndex] - 'a'] == 0){
sum1 = 0;
startIndex = endIndex + 1;
continue;
}
sum1 += s[endIndex] - 'a';
if (endIndex - startIndex + 1 == p.Length){
if(sum1 == sum) list.Add(startIndex);
sum1 -= s[startIndex++] - 'a';
}
}
return list;
}
}