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)