Back to Sliding Window
Medium
Permutation in String
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`.
Examples
Input:s1 = "ab", s2 = "eidbaooo"
Output:true
s2 contains one permutation of s1 ("ba").
Input:s1 = "ab", s2 = "eidboaoo"
Output:false
The characters "a" and "b" are not contiguous in s2.
Constraints
1 <= s1.length, s2.length <= 10^4s1 and s2 consist of lowercase English letters.
Approach
Iterate through `s2` and extract every substring of length `s1.length`. Sort the characters of both `s1` and the extracted substring, then compare them. If they match, `s2` contains a permutation of `s1`.
Complexity Analysis
Time Complexity
O((n - m) * m log m)
Space Complexity
O(m)
n is the length of s2 and m is the length of s1. This approach is very inefficient.
Solution.java
class Solution { public boolean checkInclusion(String s1, String s2) { if (s1.length() > s2.length()) return false; char[] s1Chars = s1.toCharArray(); Arrays.sort(s1Chars); String sortedS1 = new String(s1Chars); for (int i = 0; i <= s2.length() - s1.length(); i++) { String sub = s2.substring(i, i + s1.length()); char[] subChars = sub.toCharArray(); Arrays.sort(subChars); String sortedSub = new String(subChars); if (sortedS1.equals(sortedSub)) { return true; } } return false; }}