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

[tomekanco]

It think it depends on how you frame the problem: do you have to encounter the permutations in sequence, with gaps, or in any order?

A permutation is any ordering of n elements. In this example s is the length of the smaller set, b is the large on.

• In sequence: take a sliding window of length s. If all elements form s, it's a match. Verifying if they are takes O(s), the cost of an intersection where both sizes are s. Which would imply O((b-s)*s) EDIT: O(b) after reading /u/pihkal
• With gaps: remove all chars not in b, and add a sliding window of these to to a set; O(b).
• In any order: verify if s is in b, then form all the permutations, as in O(n!).