Check Permutation

Easy

0/40

33 upvotes

Asked in companies

Problem statement

For a given two strings, 'str1' and 'str2', check whether they are a permutation of each other or not.

Permutations of each other

Two strings are said to be a permutation of each other when either of the string's characters can be rearranged so that it becomes identical to the other one.

Example: 
str1= "sinrtg" 
str2 = "string"

The character of the first string(str1) can be rearranged to form str2 and hence we can say that the given strings are a permutation of each other.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a string without any leading and trailing spaces, representing the first string 'str1'.

The second line of input contains a string without any leading and trailing spaces, representing the second string 'str2'.

Note:

All the characters in the input strings would be in lower case.

Output Format:

The only line of output prints either 'true' or 'false', denoting whether the two strings are a permutation of each other or not.

You are not required to print anything. It has already been taken care of. Just implement the function.

Constraints:

0 <= N <= 10^6
Where N is the length of the input string.

Time Limit: 1 second

Sample Input 1:

abcde
baedc

Sample Output 1:

true

Sample Input 2:

abc
cbd

Sample Output 2:

false

Approaches (1)

Approach 1

Frequency Array Approach

The first and the foremost condition for two strings to be the permutations of each other is that the frequency of each element in both of them should be the same.
It can be proven by a very simple argument that we are only rearranging the letters, and not adding or deleting any character.
So we allocate an array of size 256 (that is the number of distinct ASCIIacharactersterst to store the frequency.
For the first string, we increase the frequency of each of the characters and for the second one, we decrease one for every character encountered.
In the end, we check that each of the elements of this frequency array is 0 (total additions by the first string are exactly nullified by the second string).
If it is not zero we return false else we return true.

Time Complexity

Space Complexity

(100% EXP penalty)

Check Permutation

Console