מריה בוטוסוב

יש 2 מחרוזות. יש למצואה את כל האנאגרמות של מחקוזת ראשונה במחרוזת שניה. לדוגמה: מחרוזת ראשונה: "cbaebabacd" מחרוזת שניה: "abc" תשובה: [0,6]

//s: "cbaebabacd" p: "abc"
public IList<int> findAnagrams(string s, string p) {
    List<int> result = new List();
    int[] map = new int[26];
    foreach(char c in p) {
        map[c-'a']++;
    }
    //window sliding technique
    //left and right pointer with count
    //when count is zero - we found anagram
    int left=0, right=0,count=p.Length;
    while(right<s.Length) {
        //map[right] will be positive only if letter exists as anagram
        if(map[s[right++]-'a']-- > 0) count--;
        //if count is zero - we found it
        if(count == 0) result.Add(left);
        //move left if our window length equal to p.lenght
        //add 1 back (because it's removed in previous step)
        //if map large than zero -> add count back
        if(right - left == p.Lenght && map[s[left++]-'a']++>=0) count++;
    }
}