< 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.