567 Permutation in String

1. Description

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.

Constraints:

1. \(1 \leq s1.length, s2.length \leq 10^{4}\)
2. s1 and s2 consist of lowercase English letters

1.1. Examples:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

2. Solution

2.1. Understanding the problem

Well a trivial case is if len(s1) > len(s2), then we return false.

I think we can just use brute force and scan s2 with a sliding window s2[slow:fast], where fast-slow == len(s1), and check if s1 is a permutation of the window.

How to check for permutation? I think we should first check if set(s1) == set(s2[slow:fast]), then check sum([ord(c) for c in s1]) == sum([ord(c) for c in window]).

2.2. Algorithm

2.3. Code

Listing 1: 567 Permutation in String Problem question my solution

def checkInclusion(s1, s2):
    """
    :type s1: str
    :type s2: str
    :rtype: bool
    """

    if len(s1) > len(s2):
        return False

    fast = 0
    slow = 0

    while fast - slow < len(s1):
        fast += 1

    while fast <= len(s2):
        window = s2[slow:fast]
        if (set(s1) == set(window)) and (
            sum([ord(c) for c in s1]) == sum([ord(c) for c in window])
        ):
            return True
        fast += 1
        slow += 1

    return False


# tests
s1 = "abc"
s2 = "a"
print(checkInclusion(s1, s2) == False)


s1 = "abc"
s2 = "abc"
print(checkInclusion(s1, s2) == True)

s1 = "abc"
s2 = "bca"
print(checkInclusion(s1, s2) == True)

s1 = "abc"
s2 = "bcae"
print(checkInclusion(s1, s2) == True)

s1 = "abc"
s2 = "bbcda"
print(checkInclusion(s1, s2) == True)

Listing 2: 567 Permutation in String Problem question my solution-results

True
True
True
True
False

2.3.1. Complexity

2.3.1.1. Time complexity:

I'm not too sure about this but I think this is \(O(N^{2})\) as worst case we need to do \(N \over 2\) sum during a full scan.

2.3.1.2. Space complexity:

O(N).

2.4. Leetcode solution

nil.

Listing 3: 567 Permutation in String Problem question leetcode solution

<<imports for typing>>

Listing 4: 567 Permutation in String Problem question leetcode solution-results

2.4.1. Time complexity:

2.4.2. Space complexity:

3. More analysis

3.1. General thoughts

3.2. Related problems

4. Log time