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 of s1 in s2.

• 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 decrement required 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), until required 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 size s1, 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.