Permutation In String - Leetcode Solution

Problem Statement:

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

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

Solution:

To solve this problem, we need to check whether the given substring s2 contains a permutation of s1. A permutation of s1 can be of any length, so we will use a sliding window approach to compare all the substrings of s2.

The basic idea of the sliding window approach is to maintain a window of size n (length of string s1) and slide it through the string s2. We will check at each iteration if the current window contains a valid permutation of s1. To achieve this, we will use a frequency map to count the occurrences of characters in s1 and s2.

We will create a hash array of size 26 to store the character count of s2. This hash array will represent the frequency map of s2. We will then slide the window of length s1.length() through the string s2 and check the frequency of characters in the current window. If the frequency of characters in the current window is same as that of the frequency map of s1, then it is a valid permutation of s1.

If we find a valid permutation in any of the substrings of s2, we will return true. Otherwise, we return false.

Algorithm:

1. Create a hash array of size 26 to store the character count of s2.
2. Fill the hash array with the character count of s1.
3. Traverse through the string s2 using a sliding window approach.
4. For each window of size s1.length(), check the frequency count of characters and compare it with the hash array.
5. If the frequency count of characters in the current window matches the hash array, return true.
6. If we reach the end of s2 without finding a valid permutation, return false.

Pseudocode:

int s1Length = s1.length(); int s2Length = s2.length();

int[] hashArray = new int[26];

// Fill hash array with count of each character in s1 for (int i=0; i<s1Length; i++) { hashArray[s1.charAt(i)-'a']++; }

int left = 0, right = 0;

// Traverse through s2 using sliding window approach while (right<s2Length) {

// Slide window to right by 1 character hashArray[s2.charAt(right)-'a']--;

// If window size exceeds s1.length(), slide window to left by 1 character if (right-left+1 > s1Length) { hashArray[s2.charAt(left)-'a']++; left++; }

// If current window contains valid permutation, return true if (right-left+1 == s1Length && Arrays.equals(hashArray, new int[26])) { return true; }

// Move the right pointer to the next character right++; }

// If no valid permutation found, return false return false;

Time Complexity:

The time complexity of this algorithm is O(s2.length()) where s2 is the length of the second string. We traverse through the string s2 only once and perform a constant time operation for each character.

Space Complexity:

The space complexity of this algorithm is O(1) as we are using a constant size hash array of 26. The space taken by other variables is also constant. Hence, the overall space complexity is O(1).

Conclusion:

In this problem, we have learned how to use a sliding window approach to check whether a given substring contains a permutation of another string. By using a frequency map, we can count the occurrences of characters in each string and compare them to find a valid permutation.

1