567 Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").
Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note: 1. The input strings only contain lower case letters. 2. The length of both given strings is in range [1, 10,000].

Brute Force Approach: Every substring of length |s1| in |s2| and find at least one instance of where the sorted substring == sorted s1.

Time Complexity: Let s1 be len(s1) and s2 be len(s2). O((s1-s2)*s1logs1 + s1(s1-s2)) for sorting each substring and string comparison.

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

    sorted_s1 = sorted(s1)
    go_till = len(s2) - len(s1) + 1
    for i in range(0, go_till):
        if sorted_s1 == sorted(s2[i:i+len(s1)]):
            return True

    return False

Last updated