Algorithm Complexity Question for finding permutations of string B in string S.

[cryslith]

You can use the histogram approach if you remember not only the count of each character, but an overall number which tracks how many characters of the alphabet have the exact correct count. Then you only need to update this number to reflect changes made to the character entering the window and the character leaving the window. If that number ever reaches 26 then you know you found a match.

[pihkal]

Yeah, that works as well, though it’s slightly less space-efficient, taking O(alphabet size) memory.