Permutation in String

Problem Statement

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

You should aim for a solution with O(n) time and O(1) space, where n is the maximum of the lengths of the two strings.

Recommended Time and Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the maximum of the lengths of the two strings.

Hint 1

A brute force solution would be to check every substring of s2 with s1 by sorting s1 as well as the substring of s2. This would be an O(n^2) solution. Can you think of a better way? Maybe we can use the frequency of the characters of both the strings as we did in checking anagrams.

Hint 2

We return false if the length of s1 is greater than the length of s2. To count the frequency of each character in a string, we can simply use an array of size O(26), since the character set consists of a through z (26 continuous characters). Which algorithm can we use now?

Hint 3

We use a sliding window approach on s2 with a fixed window size equal to the length of s1. To track the current window, we maintain a running frequency count of characters in s2. This frequency count represents the characters in the current window. At each step, if the frequency count matches that of s1, we return true.

Solution

Brute Force

def check_inclusion_brute_force(s1: str, s2: str) -> bool:
    s1 = sorted(s1)
    for i in range(len(s2)):
        for j in range(i, len(s2)):
            sub_str = s2[i : j + 1]
            sub_str = sorted(sub_str)
            if sub_str == s1:
                return True
    return False

Time complexity: O(n^3 log n) Space complexity: O(n)

Hash Table

def check_inclusion_hash_table(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
        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]]:
                break
            if count1.get(s2[j], 0) == count2[s2[j]]:
                cur += 1
            if cur == need:
                return True
    return False

Time complexity: O(n * m) Space complexity: O(1)

Sliding Window

def check_inclusion_sliding_window(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    s1_count, s2_count = [0] * 26, [0] * 26
    for i in range(len(s1)):
        s1_count[ord(s1[i]) - ord('a')] += 1
        s2_count[ord(s2[i]) - ord('a')] += 1

    matches = 0
    for i in range(26):
        matches += (1 if s1_count[i] == s2_count[i] else 0)

    l = 0
    for r in range(len(s1), len(s2)):
        if matches == 26:
            return True

        index = ord(s2[r]) - ord('a')
        s2_count[index] += 1
        if s1_count[index] == s2_count[index]:
            matches += 1
        elif s1_count[index] + 1 == s2_count[index]:
            matches -= 1

        index = ord(s2[l]) - ord('a')
        s2_count[index] -= 1
        if s1_count[index] == s2_count[index]:
            matches += 1
        elif s1_count[index] - 1 == s2_count[index]:
            matches -= 1
        l += 1
    return matches == 26

Time complexity: O(n) Space complexity: O(1)