In this problem we have pattern S and a string T and we want to search the anagrams of S in T. ========================================================================= Tip 1: Given two strings A and B, how do you check that they are anagrams? ========================================================================= Solution Tip 1: Three algorithms: - sort both sequence and compare them - count for each letter how many times it appears in A and in B - same as above but count how many times it appears in A minus how many times it appears in B Some of these algorithms might be easier than other to translate into sliding window algorithms. ========================================================================= Tip 2: We will use a sliding window approach maintaining for each character how many times it appears in the windows minus how many times it appears in the pattern, what are the changes when the sliding window shifts? How fast can we detect if the current window is a match? ========================================================================= Solution Tip 2: We use an array freq of size 256 to maintain the differences. To insert a char c we do freq[c]++ and to remove it we do freq[c]--. To keep track of whether the current window is a match we need to count how many char c have freq[c]≠0, how do we do that? ========================================================================= Solution bis Tip 2: We have a counter nbCharNotMacthing, each time we modify freq[c] we remove one if freq[c]≠0, then we modify freq[c] then we readd one if freq[c]≠0.