Permutation in String

aniket verma
Last Updated: May 13, 2022

Introduction

In this blog, we will discuss how to find the Permutation in String. It’s a significant problem to check your understanding of hashing and strings. Such questions are frequently asked in interviews and is a fundamental problem.

Before solving the problem, it’s recommended to understand hashmaps, strings, and the sliding window technique. In this blog, we will dive deep into each detail to get a firm hold over the application of strings and hashing in problems.  

Let’s look at the problem statement.

You are given two strings s1 and s2, containing only lowercase characters. The task is to determine whether any permutation of the string s1 is a  substring of s2. Return true if the condition satisfies; otherwise, return false.


Let’s understand the problem using an example.

Input:  strings s1 = “ab”   and s2 = “eidbaooo”

Output true

Explanation: Since the permutation of s1, i.e., “ba” is a substring of s2.

Naive Approach

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach.

So, the basic approach is to find all permutations of the string s1. For each permutation, we will check if it’s a substring of the string s2. 

So the naive/basic approach could be formulated as:

  1. Find all the permutations of s1.
  2. Return true if any permutation is a substring of the string s2.
  3. If None of the permutations is a substring of the string s2, return false. 

Now let’s look at the PseudoCode.

PseudoCode

Algorithm

___________________________________________________________________

procedure PermutationInString(s1, s2):

___________________________________________________________________

1.    for each permutation in permutations(s1) do  

2.        if isSubstring(permutation, s2) do # return true if it’s a substring of s2 

3.          return true    

4.     end if   

5.  return false

6end procedure

___________________________________________________________________

CODE IN C++

//C++ program to solve the problem Permutation In String
#include <bits/stdc++.h>
using namespace std;

// function to solve the problem Permutation In String 
bool PermutationInString(string &s1, string &s2){
    // Sort the string in lexicographically
    // ascending order
    sort(s1.begin(), s1.end());
    // iterate over each permutation of s1    
    do {
     // if current s1 permutation is a substring of s2 then return true    
      if(s2.find(s1) != string::npos)
            return 1;
    } while (next_permutation(s1.begin(), s1.end()));
    
    // if none of the permutations are a substring of  s2 return false
    return 0;
}
int main() {    
    // 2 strings given are
    string s1 = "ab";
    string s2 = "eidbaooo";
    
    if(PermutationInString(s1, s2)){
        cout<<"The string s1 has a permuatation as a substring of s2\n";
    }else{
        cout<<"There is no permuatation of s1 which is a substring of s2\n";
    }
    return 0;
}

 

Output

The string s1 has a permuatation as a substring of s2

Complexity Analysis

Time Complexity: O(|s1|! * |s1|*|s2|)

This is because we iterate through all permutations, and we are checking if s1 is a substring of s2.

Space complexity: O(|s1|+|s2|) at the worst case to store the characters of the string s1 and s2.

The above algorithm works in exponential time, which is pretty slow. This gives us the motivation to improve our algorithm.

So let’s think about an efficient approach to solve the problem.

Efficient Approach

If we want to build up an efficient solution, we will need to find out if there is any redundancy or any repetition that we are doing. The redundancy in our code is that we check each permutation of the string s1 if it’s a substring of the string s2. We can make some observations that we can infer to get rid of the extra redundant computation.

Notice that when we are iterating over each permutation, we are just rearranging the characters of the string s1 and checking whether the rearranged string s1 is a substring of the string s2. This means that if a permutation of the string s1 exists as a substring of s2, then s2 must contain a substring with exactly the same characters as that of s1 in no particular order.

We can conclude this statement because we just have to tell whether any permutation of the string s1, meaning any rearranged form of the string s1, exists as a substring of s2. So it helps us realize the fact that no matter the order of characters in s1, the substring of s2 must have the same characters as that of the string s2 in no particular order. Also, the length of the s1 and its permutation found as a substring in the string s2 must be equal.   

So we can store the characters of the string s1 in a hash map and iterate over all substrings in s2  having the size |s1|. One way is to find all substrings of s2 having size |s1| and then check the count of all characters in s1.

But this can also be solved using the sliding window technique efficiently.

Iterate over the window of size |s1| and check if the count of all characters matches. If it matches, then return true. Otherwise, we can decrease the count of the character at the starting of the window and increase the count of the next incoming character.  

Now we can formulate our approach :

  1. Store the count of all characters of s1 in a hash map.
  2. Iterate over the string s2 in a sliding window manner with a window size of |s1|.
  3. If the count of all characters matches, return true.
  4. Otherwise, decrement the count of the character at the starting of the window and increment the count of the next character.  
  5. If no further substring is left in s2 to be traversed, return False.   

Let’s look at the Code.

CODE IN C++

//C++ program to solve the problem Permutation In String
#include <bits/stdc++.h>
using namespace std;

// function to solve the problem Permutation In String 
bool PermutationInString(string &s1, string &s2){
    if(s2.size()<s1.size()) return 0; // return false if the size of s2 is less than that of s1
    vector<int> hashmap(26, 0); // maintain a hashmap of size 26 
    // store the count of all characters in the hashmap
    for(char c:s1)
        hashmap[c-'a']++;
    // another hashmap to maintain the count of window characters of size |s1|  
    // to efficiently match the count of characters in hashmap
    vector<int> hashmap2(26, 0);
    
    // store the count of characters 
    for(int i=0;i<s1.size();++i) 
        hashmap2[s2[i]-'a']++;
    // slide over the window of size |s1|     
    for(int i=s1.size(); i<s2.size();++i){
        int count =0;
        // store the count of all characters whose frequency match 
        for(int j=0;j<26;++j){
            count+=(hashmap[j]==hashmap2[j]);
        }
        // if count == 26 means we have found a permutation 
        // that is a substring of s2
        if(count==26) return 1;
        // decrement the count of starting character of the window
        hashmap2[s2[i-s1.size()]-'a']--;
        // increment the count of next incoming character 
        hashmap2[s2[i]-'a']++;
    }
    // check at last if the count of all characters in both hashmaps match in the end
    int count =0;
    for(int j=0;j<26;++j){
        count+=(hashmap[j]==hashmap2[j]);
    }
        
    // return 1 if the count is 26 else return 0
    if(count==26)return 1;
    return 0;
}
int main() {
    // 2 strings given are
    string s1 = "ab";
    string s2 = "eidbaooo";
    
    if(PermutationInString(s1, s2)){
        cout<<"The string s1 has a permuatation as a substring of s2\n";
    }else{
        cout<<"There is no permuatation of s1 which is a substring of s2\n";
    }
    return 0;
}

 

Output

The string s1 has a permuatation as a substring of s2

Complexity Analysis

Time Complexity: O(|s2|)

We are traversing the whole string s2 in the worst case.

Space complexity: O(1) as we are using constant memory to store the count of characters.

Hence we reached an efficient solution from an exponential solution. 

Frequently Asked Questions

Q1. When is the Sliding window technique useful?  

Answer) The sliding window technique is useful when you need to keep track of a contiguous sequence of elements that we used in the current blog.

 

Q2. Why is hashing important?                                                                                                                                            

Answer) Hashing is very useful and important because it helps store key-value pairs, increasing the solution’s efficiency and providing fast checks.  

 

Q3. How often are strings asked in interviews?                                                                                                               

Answer) String is a favorite topic of the top companies, including Apple, Google, Amazon, etc. It is often asked in interviews and questions that are formed on strings, usually club 2-3 essential concepts as discussed in the blog. 

Key Takeaways

This article taught us how to solve the problem of Permutation In String. We also saw how to approach the problem using a naive approach followed by an efficient solution. We discussed an iterative implementation using examples, pseudocode, and proper code in detail.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out how we can apply hashing in strings and the sliding window technique to simplify our task and make fewer comparisons. 

Now, we recommend you practice problem sets based on the concepts of Permutation In String to master your fundamentals. You can get a wide range of questions similar to the problem Permutation In String on CodeStudio

Happy Learning!!

Was this article helpful ?
0 upvotes