Permutation In String

Question

You are given two strings s1 and s2.

Return true if s2 contains a permutation of s1, or false otherwise. That means if a permutation of s1 exists as a substring of s2, then return true.

Both strings only contain lowercase letters.

Example 1:

Input: s1 = "abc", s2 = "lecabee"

Output: true

Explanation: The substring "cab" is a permutation of "abc" and is present in "lecabee".

Example 2:

Input: s1 = "abc", s2 = "lecaabee"

Output: false

Constraints:

• 1 <= s1.length, s2.length <= 1000

Solution

Intuition

We can first build a window of s1 and keep sliding until we find the permutation. For permutation we can basically use something like Counter(a) == Counter(b)

[!DANGER]
If we do Counter(a) == Counter(b) it only works for python 3.10+. For Python 3.09 below, it treat missing key { x: 0 } as a real match so might be wrong. The best solution is use an array of 26 and compare using ord()

Implementation

class Application:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if not s1: 
            return True

        if len(s1) > len(s2):
            return False
        
        s1Frequency = [0] * 26
        windowFrequency = [0] * 26
        
        slow, fast = 0, 0

        for letter in s1:
            s1Frequency[self._id(letter)] += 1
            
        while fast < len(s2):
            windowFrequency[self._id(s2[fast])] += 1

            if fast >= len(s1):
                windowFrequency[self._id(s2[slow])] -= 1
                slow += 1
            
            if self._isPermutation(s1Frequency, windowFrequency):
                return True
            
            fast += 1
        
        if self._isPermutation(s1Frequency, windowFrequency):
            return True
            
        return False
    
    def _id(self, x: str) -> int:
        return ord(x) - ord('a')
        
    def _isPermutation(self, s1Frequency: Dict[str, int], windowFrequency: Dict[str, int]):
        return s1Frequency == windowFrequency

Note that in here, if we build the fast pointer first and then loop again i.e

while fast < len(s1):
    windowFrequency[self._id(s2[slow])] += 1
    windowFrequency[self._id(s2[fast])] += 1

while fast < len(s2):
    # Fast here already advanced 1 step ahead
    ...

You're gonna see a problem that our fast pointer actually advanced 1 step ahead when it comes to main while fast < len(s2) logic.

The solution for this is don't traverse first and merge in later, traverse at 1 go

Time complexity:

• Time: $O(n)$
• Space: $O(26) = O(1)$