LC 567 - Permutation in String

Question

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true

Explanation: s2 contains one permutation of s1 (“ba”).

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

• 1 <= s1.length, s2.length <= 104
• s1 and s2 consist of lowercase English letters.

Links

Question here and solution here

Solution

concept

There are 2 main ways to solve this.

The first way is to maintain two hash map that stores the char frequency of the the 2 string. We will then iterate s2 in two for loops to check if there is a matching string starting at each of the inner for loop. Once we notice that the current inner loop’s window has more (a certain) char in s2 than s1 we will start the next window at outer loop since as window expand the count of that char in s2 will only increase so it will never match s1. (this solution is TLE at the moment)

The second way involving a hash map and sliding window. The general concept is we maintain a window size of len(s1) and check if the char count of s1 is the same as the window of s2. There are several ways to optimize this to bring time complexity to $O(n)$

code

class NeetSolution:
	"""
	pure hash map
	Time complexity: O(n∗m)O(n∗m)
	Space complexity: O(1)O(1) since we have at most 26 different characters.
	Where nn is the length of the string1 and mm is the length of string2.
	
	TLE
	"""
    def checkInclusion(self, s1: str, s2: str) -> bool:
        count1 = {}
        for c in s1:
            count1[c] = 1 + count1.get(c, 0)
        
        need = len(count1)
        for i in range(len(s2)):
            count2, cur = {}, 0 # each start is a new window
            for j in range(i, len(s2)):
                count2[s2[j]] = 1 + count2.get(s2[j], 0)
                if count1.get(s2[j], 0) < count2[s2[j]]: # window has more char of j in s2, there is no recovery so restart from outer loop
                    break
                if count1.get(s2[j], 0) == count2[s2[j]]:
                    cur += 1
                if cur == need:
                    return True
        return False

class NeetSolution:
	"""
	hash map + sliding window
	Time complexity: O(n)
	Space complexity: O(1)
	"""
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        # get the char count for both str
        s1Count, s2Count = [0] * 26, [0] * 26
        for i in range(len(s1)):
            s1Count[ord(s1[i]) - ord('a')] += 1
            s2Count[ord(s2[i]) - ord('a')] += 1
        # has to go through this once to get the matches first
        # subsequently we only track matches
        matches = 0
        for i in range(26):
            matches += (1 if s1Count[i] == s2Count[i] else 0)
        
        l = 0
        for r in range(len(s1), len(s2)):
            if matches == 26:
                return True
            # right pointer movement
            index = ord(s2[r]) - ord('a')
            s2Count[index] += 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] + 1 == s2Count[index]:
                matches -= 1
			# left pointer movement
            index = ord(s2[l]) - ord('a')
            s2Count[index] -= 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] - 1 == s2Count[index]:
                matches -= 1
            l += 1
        return matches == 26

class MySolution:
	"""
	similar to the above hash map + sliding window
	but we check the whole hashmap everytime
	Time complexity: O(26n)
	Space complexity: O(1)
	"""
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1_counter = {}
        for c in s1:
            if c in s1_counter:
                s1_counter[c] += 1
            else:
                s1_counter[c] = 1
        
        s2_counter = {}
        l, r = 0, 0
        for r in range(len(s2)):
            if s2[r] in s2_counter:
                s2_counter[s2[r]] += 1
            else:
                s2_counter[s2[r]] = 1

            while r - l + 1 > len(s1):
                if s2_counter[s2[l]] == 1:
                    del s2_counter[s2[l]]
                else:
                    s2_counter[s2[l]] -= 1
                l += 1

            if s1_counter == s2_counter:
                return True

        return False

Complexity

time: $O(n)$
space: $O(1)$