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:
- Find all the permutations of s1.
- Return true if any permutation is a substring of the string s2.
- 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
6. end 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 s2Complexity 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.
Also check out - Substr C++
305+ registered