Permutation in String

1. The obvious way

   Sort every window of s2 and compare with sorted s1: O(n x m log m).

2. The key insight

   Count the letters of s1 (the rack). Slide a window of the same length along s2, adding the entering letter and removing the leaving one. Whenever the window's tally equals the rack's tally the window is a permutation. Comparing two 26-slot tallies is quick, so the whole scan is linear.

3. The algorithm
   1. Short text longer than the long one? Answer False.
   2. Tally the letters of s1.
   3. Slide a same-length window along s2: add the letter entering, remove the letter leaving.
   4. After each slide, window tally equals the s1 tally? Answer True.

Watch it run

frame {e, i}

def check_inclusion(s1, s2):
    size = len(s1)
    if size > len(s2):
        return False
    rack = [0] * 26
    frame = [0] * 26
    for letter in s1:
        rack[ord(letter) - ord("a")] += 1
    for position, letter in enumerate(s2):
        frame[ord(letter) - ord("a")] += 1                       # letter enters
        if position >= size:
            frame[ord(s2[position - size]) - ord("a")] -= 1      # letter leaves
        if frame == rack:
            return True
    return False

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.