Permutation in String
MedPrompt
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 <= 104s1ands2consist of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach is based on the property that two strings are permutations of each other if and only if their sorted versions are identical. We can iterate through all substrings of s2 that have the same length as s1. For each substring, we sort it and compare it with a pre-sorted version of s1.
Algorithm
- Let
nbe the length ofs1andmbe the length ofs2. - If
n > m, it's impossible fors2to contain a permutation ofs1, so returnfalse. - Convert
s1to a character array and sort it. This gives a canonical representation ofs1's permutations. - Iterate through
s2with a window of sizen. The loop runs fromi = 0tom - n. - For each window (substring of
s2fromitoi + n - 1):- Convert the substring to a character array and sort it.
- Compare the sorted substring with the sorted
s1. - If they are identical, it means the substring is a permutation of
s1. Returntrue.
- If the loop completes without finding any match, return
false.
Walkthrough
The core idea is to check every possible substring of s2 of length s1.length() and see if it's an anagram of s1. A reliable way to check for anagrams is to sort both strings and see if they become equal. While simple, this method involves a costly sorting operation inside a loop, which affects its performance significantly.
import java.util.Arrays; class Solution { public boolean checkInclusion(String s1, String s2) { if (s1.length() > s2.length()) { return false; } int n = s1.length(); int m = s2.length(); char[] s1Chars = s1.toCharArray(); Arrays.sort(s1Chars); for (int i = 0; i <= m - n; i++) { char[] subChars = s2.substring(i, i + n).toCharArray(); Arrays.sort(subChars); if (Arrays.equals(s1Chars, subChars)) { return true; } } return false; }}Complexity
Time
O((m-n) * n log n). Let `n` be the length of `s1` and `m` be the length of `s2`. Sorting `s1` initially takes `O(n log n)`. The main loop runs `m-n+1` times. Inside the loop, creating a substring takes `O(n)` and sorting it takes `O(n log n)`. This dominates, leading to the overall complexity.
Space
O(n), where `n` is the length of `s1`. This space is required to store the character arrays for `s1` and the substrings of `s2` for sorting.
Trade-offs
Pros
Conceptually straightforward and easy to implement.
Cons
Highly inefficient for large strings due to the repeated sorting of substrings within a loop.
Very likely to result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
Solutions
Solution
class Solution { public boolean checkInclusion ( String s1 , String s2 ) { int n = s1 . length (); int m = s2 . length (); if ( n > m ) { return false ; } int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < n ; ++ i ) { -- cnt [ s1 . charAt ( i ) - 'a' ]; ++ cnt [ s2 . charAt ( i ) - 'a' ]; } int diff = 0 ; for ( int x : cnt ) { if ( x != 0 ) { ++ diff ; } } if ( diff == 0 ) { return true ; } for ( int i = n ; i < m ; ++ i ) { int a = s2 . charAt ( i - n ) - 'a' ; int b = s2 . charAt ( i ) - 'a' ; if ( cnt [ b ] == 0 ) { ++ diff ; } if (++ cnt [ b ] == 0 ) { -- diff ; } if ( cnt [ a ] == 0 ) { ++ diff ; } if (-- cnt [ a ] == 0 ) { -- diff ; } if ( diff == 0 ) { return true ; } } return false ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.