Permutation in String Leetcode Solution

Table of Contents

Problem Statement :

Permutation in String Leetcode Solution – 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 :

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 :

Observation :

We need to check that s2 contains a substring that is a permutation of s1.
The permutation of a string means reordering the string’s letters. This means that all permutations of a string are the Anagrams of the string.
And we have to find whether such a substring exists in s2 which is a permutation of s1, which means we have to find a substring in s2 such that the frequency of characters in that substring is the same as the frequency of characters in s1.
From the above observation, we can see that we can use the SLIDING WINDOW APPROACH to find the window in s2 which has the same frequency of characters as s1.

Algorithm :

First, we will initialize two frequency maps. One for string s1 and another for string s2.
Store the frequency of all characters of strings s1 in s1FrequencyMap.
Now, create a second frequency map i.e. s2FrequencyMap that will help us maintain the frequency of the s2 substring, and the length of that substring will always be of the size of s1.
We will use two pointers i and j, i will help us to acquire the characters of s2, and j will help us to release the characters of s2.
Initialize acquiring and releasing pointers with -1 i.e. i = – 1 and j = -1.
Now, move your acquire pointer ( i ) until we acquire the s1.length-1 character in the s2 string.
We will be continuing the below steps until we reach a situation where the end of the window reaches the end of s2. That means we will be doing the steps while j < length of s2-1.

a. Increase the acquire pointer ( i )and acquire the current character of s2 and store it in s2FrequencyMap.

b.Now check that all acquired characters in s2 are anagrams of s1. That means the frequency of current window characters in s2 is equal to s1 frequency characters, if they are equal then return true.

c. If the frequency of the characters in s1 and the current window characters in s2 do not match, we have to create the next window. So, increment the release pointers (j) and release the current characters of s2 where our releasing pointer (j) points.

8. If the algorithm doesn’t return true for any of the windows, we’ll end up here (out of the loop). This would mean that we did not find such an option in s2, then return false.

Code for Permutation in String

Java Code

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n=s1.length();
        int m=s2.length();
      // If s1 length > s2 length  
        if(n>m)return false;
      //Create two HashMap for s1 and s2
        HashMap<Character,Integer>s1FrequencyMap=new HashMap<>();
        HashMap<Character,Integer>s2FrequencyMap=new HashMap<>();
      // Fill s1frequencyMap
        for(char ch:s1.toCharArray()){
            s1FrequencyMap.put(ch,s1FrequencyMap.getOrDefault(ch,0)+1);
        }
      // create a window for the size s1
        int i=0;
        int j=-1;
        for(;i<n-1;i++){
            char ch=s2.charAt(i);
            s2FrequencyMap.put(ch,s2FrequencyMap.getOrDefault(ch,0)+1);
        }
       //Acquire and Relase Strategy or Sliding Window 
        i--;
        while(i<m-1){
            i++;
          char ch=s2.charAt(i);
             s2FrequencyMap.put(ch,s2FrequencyMap.getOrDefault(ch,0)+1);
            if(isPermutation(s1FrequencyMap,s2FrequencyMap)){
                return true;
            }
            j++;
             ch=s2.charAt(j);
            s2FrequencyMap.put(ch,s2FrequencyMap.get(ch)-1);
            if(s2FrequencyMap.get(ch)==0)s2FrequencyMap.remove(ch);
            
        }
        return false;
        
    }
    public boolean isPermutation(HashMap<Character,Integer>s1FrequencyMap,HashMap<Character,Integer>s2FrequencyMap){
        for(int i=0;i<26;i++){
            char ch=(char)(i+'a');
            int f1=s1FrequencyMap.getOrDefault(ch,0);
            int f2=s2FrequencyMap.getOrDefault(ch,0);
            if(f1!=f2)return false;
        }
        return true;
    }
}

C++ Code

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
         int n=s1.size();
        int m=s2.size();
      // If s1 length > s2 length  
        if(n>m)return false;
      //Create two HashMap for s1 and s2
         vector<int> s1FrequencyMap(26, 0);
         vector<int> s2FrequencyMap(26, 0);
      // Fill s1frequencyMap
        for(char ch:s1){
            s1FrequencyMap[ch-'a']++;
        }
      // create a window for the size s1
        int i=0;
        int j=-1;
        for(;i<n-1;i++){
            char ch=s2[i];
            s2FrequencyMap[ch-'a']++;
        }
       //Acquire and Relase Strategy or Sliding Window 
        i--;
        while(i<m-1){
            i++;
          char ch=s2[i];
             s2FrequencyMap[ch-'a']++;
            if(isPermutation(s1FrequencyMap,s2FrequencyMap)){
                return true;
            }
            j++;
             ch=s2[j];
            s2FrequencyMap[ch-'a']--;
           
            
        }
        return false;
    }
    
     bool isPermutation(vector<int> s1FrequencyMap, vector<int> s2FrequencyMap){
        for(int i=0;i<26;i++){
            if(s1FrequencyMap[i]!=s2FrequencyMap[i]) return false;
        }
        return true;
    }
};

Complexity Analysis for Number of Closed Islands Leetcode Solution

Time Complexity

O(m+n), where n is the length of string $s_{1}$ and m is the length of string $s_{2}$ .

Space Complexity

O, s1FrequencyMap and of size 26 is used.