Permutation in String
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.
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 returns true. Otherwise, we can decrease the count of the character at the start of the window and increase the count of the next incoming character.
Now we can formulate our approach :
- Store the count of all characters of s1 in a hash map.
- Iterate over the string s2 in a sliding window manner with a window size of |s1|.
- If the count of all characters matches, return true.
- Otherwise, decrement the count of the character at the start of the window and increment the count of the next character.
- 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 s2Complexity 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.
You can also read about the Longest Consecutive Sequence.
Frequently Asked Questions
When is the Sliding window technique useful?
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.
Why is hashing important?
Hashing is very useful and important because it helps store key-value pairs, increasing the solution’s efficiency and providing fast checks.
How often are strings asked in interviews?
The 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.
Conclusion
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.
Check out this problem - Longest String Chain
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.
Recommended Reading:
- Introduction to Hashing
- Top String Coding Interview Questions
- Difference Between HashMap and HashTable in Java
- Kth Distinct String in an Array
- First Element Occurring K Times in an Array
- Numbers with Prime Frequencies Greater than or Equal to K
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on CodeStudio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.
Happy Learning!!
Previous Article 
