Leetcode 567. Permutation in String
Problem Explanation:
The problem is asking to find if there is a permutation of the first string s1
within the second string s2
. A permutation of a string is another string that contains same characters, but in possibly different orders. So we want to check if any possible re-arrangement of s1
exists as a substring in s2
.
Let's consider an example: s1 = "ab"
and s2 = "eidbaooo"
. Here, if we rearrange "ab", we can get the substring "ba" which is present in s2
. So, the output will be True.
Approach Explanation:
The solution uses a sliding window approach with a character count array. It works as follows:
-
We initialize a character count array. We traverse through
s1
and for each character, we increment its count in the array. -
The
required
variable is used to keep track of the number of characters required to match a permutation ofs1
ins2
. -
We use two pointers to define a sliding window in
s2
. We start by expanding the window from right side (r
) and for each character included in the window, we decrement its count in the array, and if this character is still required, we decrementrequired
as well. -
Once we have found a window with a permutation of
s1
, i.e.,required
becomes zero, we need to start shrinking the window from the left side (l
), untilrequired
is no longer zero. -
Before shrinking the window, we check if the size of window is the same as the size of
s1
, which means it is a valid permutation, and we return true. -
If we have traversed through
s2
without finding any valid window of sizes1
, we return false.
Python Solution:
1 2python 3class Solution: 4 def checkInclusion(self, s1: str, s2: str) -> bool: 5 count = [0]*26 6 required = len(s1) 7 8 for c in s1: 9 count[ord(c) - ord('a')] += 1 10 11 l = 0 12 for r in range(len(s2)): 13 if count[ord(s2[r]) - ord('a')] > 0: 14 required -= 1 15 count[ord(s2[r]) - ord('a')] -= 1 16 17 if not required: 18 while l<r and count[ord(s2[l]) - ord('a')] < 0: 19 count[ord(s2[l]) - ord('a')] += 1 20 l += 1 21 if r - l + 1 == len(s1): 22 return True 23 return False
In this Python solution, we start by initializing the count
array with zeros and increment the count for each character in s1
. For every character being considered within the window in s2
, its count in the count
array gets decremented. We also increment the left pointer l
if the count of character is negative. If required
is zero and the length of our window is equal to the length of s1
, we return True. Otherwise, return False after traversing the entire string s2
.## JavaScript Solution:
The JavaScript solution is quite similar to the Python solution. Here, the 'charCodeAt' method is used in place of 'ord' to get the ASCII value of a character.
1
2javascript
3var checkInclusion = function(s1, s2) {
4 const count = Array(26).fill(0);
5 let required = s1.length;
6
7 for (let c of s1)
8 count[c.charCodeAt() - 'a'.charCodeAt()]++;
9
10 let l = 0;
11 for (let r = 0; r < s2.length; r++) {
12 if (count[s2[r].charCodeAt() - 'a'.charCodeAt()]-- > 0)
13 required--;
14
15 if (!required)
16 while (l < r && count[s2[l].charCodeAt() - 'a'.charCodeAt()]++ < 0)
17 l++;
18
19 if (r - l + 1 === s1.length)
20 return true;
21 }
22
23 return false;
24};
In this JavaScript solution, the approach is the same as the Python solution. We initialize the count array to be of length 26 with all elements being zero. For each character in the given window in s2
, its count gets decremented and the left pointer l
gets incremented when the count of character is negative. When required
is zero and the window size is the length of s1
, return True else False.
Java Solution:
1 2java 3class Solution { 4 public boolean checkInclusion(String s1, String s2) { 5 int[] count = new int[26]; 6 int required = s1.length(); 7 8 for (char c : s1.toCharArray()) 9 count[c - 'a']++; 10 11 int l = 0; 12 for (int r = 0; r < s2.length(); r++) { 13 if (count[s2.charAt(r) - 'a']-- > 0) 14 required--; 15 16 if (required == 0) { 17 while (l < r && count[s2.charAt(l) - 'a']++ < 0) 18 l++; 19 20 if (r - l + 1 == s1.length()) 21 return true; 22 } 23 } 24 25 return false; 26 } 27}
This Java solution is very similar to the Python and JavaScript solutions. The main difference is that we need to use the 'charAt' method to access individual characters in the string, and we also have to convert the strings to character arrays when we want to iterate through them. Nevertheless, the overall logic remains the same. In the end, if there is a window of size s1
in s2
which is a permutation of s1
, the function returns true; otherwise, it returns false.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.