Permutation in String
Problem 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.
Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints:
- 1 <= s1.length, s2.length <= 104
s1ands2consist of lowercase English letters.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute-force approach involves checking all permutations of s1 and seeing if any of them is a substring of s2. Although not efficient, it helps build understanding of the problem.
- Generate all permutations of the string
s1. - Check each permutation to see if it exists as a substring in
s2.
Code:
- Time Complexity: O(n! * m) where
nis the length ofs1andmis the length ofs2. - Space Complexity: O(n), due to recursion stack and storing permutations.
2. Sorting Each Substring
Intuition:
Since a permutation of s1 should have the same characters with the same frequency, for each substring of s2 with length s1, we check if its sorted version matches the sorted s1.
- Sort
s1. - For each possible substring of
s2with the length ofs1, sort it and compare with sorteds1.
Code:
- Time Complexity: O(m * n log n), where
mis the size ofs2andnis the size ofs1. - Space Complexity: O(n), space needed to store the sorted version of
s1and each substring.
3. Sliding Window
Intuition:
The optimized approach uses a sliding window technique with two arrays (or maps) to keep track of character counts. If at any point the character counts between the current window in s2 and s1 match, we found a permutation.
- Use two counts arrays of size 26 (for each letter in the alphabet) for
s1and the current window. - Slide over
s2with a window of the size ofs1, updating the counts. - If the counts match, return true.
Code:
- Time Complexity: O(m), where
mis the length ofs2. - Space Complexity: O(1), constant space for the count arrays.