< Back




567. Permutation in String

This one is a bit tricky, but is similar to a lot of our sliding window problems that start with some
sliding window with like k length. Requires a bit of initialization and out of the box thinking, but
we still end up using a hash map to solve this problem.

Essentially, we're being asked to find if string s2 contains a permutation of string s1. So we need
to find out if some subarray of s2 contains a permutation of the characters in s1.

First we create two arrays that represent our hash map. Seeing as all the inputs are going to be
lowercase letters, we can have 2 arrays of size 26. We iterate through the length of s1, incrementing
into our hash map each time we see a character. This also sets up our sliding window, as the future
iteration through s2 will start at the end of the sliding window.

Next, we iterate through s2 for len(s2) - len(s1), we're accounting for the length of the sliding
window and avoiding out of bounds references. If the hash maps we created are equal, we return True.
If not, we continue to move the sliding window, incrementing the next character we encounter in the
hash map, and decrementing the character that is no longer in the sliding window.

The solution is as follows:


  class Solution:
      def checkInclusion(self, s1: str, s2: str) -> bool:
          n = len(s1)
          m = len(s2)

          if n > m: return False

          s1_counts = [0] * 26
          s2_counts = [0] * 26

          for i in range(n):
              s1_counts[ord(s1[i]) - ord('a')] += 1
              s2_counts[ord(s2[i]) - ord('a')] += 1

          for j in range(len(s2) - n):
              if s1_counts == s2_counts: return True
              s2_counts[ord(s2[j + n]) - ord('a')] += 1
              s2_counts[ord(s2[j]) - ord('a')] -= 1

          return s1_counts == s2_counts


_ Time Complexity:

  O(n) - We iterate through the input once.

_ Space Complexity:

  O(1) - We maintain a fixed size set of hash maps that will always occupy O(26) space.