Check if given two strings are permutation of each other

Suppose we are given two lowercase string as an input and we have to check whether they are a permutation of each other i.e if one string can be generated by changing the position of characters of the other string.

A naive approach would be to generate all possible permutation of one string(str1) and compare each and every permutation(of str1) with the other string(str2). The time complexity of this approach will be O(n!) and it is pathetically slow.

The optimized approach is to first check if both strings are of the same length. If yes, then traverse all the character of the first string (str1) and store the number of occurrences of each character in an array. Then traverse other string(str2) and decrement the occurrence of each character from the array. If the content of the final array is 0, then it means both strings are a permutation of each other, else both strings are not a permutation of each other.

Example1:
str1 = “abcdaea”      str2=”bcdaaae”
after traversing first string:
arr[0] = 3, arr[1]=1, arr[2]=1, arr[3]=1, arr[4]=1 ……..
after traversing first string:
arr[0] = 0, arr[1]=0, arr[2]=0, arr[3]=0, arr[4]=0 ……..
Hence, they are a permutation of each other

Example2:
str1 = “abcdeee”      str2=”bcdaaae”
after traversing first string:
arr[0] = 1, arr[1]=1, arr[2]=1, arr[3]=1, arr[4]=3 ……..
after traversing first string:
arr[0] = -2, arr[1]=0, arr[2]=0, arr[3]=0, arr[4]=2 ……..
Hence, they are not a permutation of each other

Algorithm

is_permutation(str1, str2):
    int occurance[27] = 0    
    //array to store the number of the occurrence of each character
   
    for i ->1 to str1.size:
       occurance[int(str1[i])-97] = occurance[int(str1[i])-97]+1   
       //int(str1[i]) ascii value of character stored at index i
    
    for i ->1 to str2.size:
       occurance[int(str2[i])-97] = occurance[int(str2[i]) - 97]-1

    for i->0 to 27
       if occurance[i]!=0
          return "not permutation";

    return "permutation";

Below is the implementation of the algorithm in CPP

#include <bits/stdc++.h>
using namespace std;

string is_permutation(string str1, string str2){

	vector<int>arr(27,0);

	if(str1.size() == str2.size()){
		
		for(int i=0; i<str1.size();i++)
			arr[int(str1[i])-97] +=1;

		for(int i=0; i<str2.size();i++)
			arr[int(str2[i])-97] -=1;

		for(int i=0;i<=27;i++) 
			if(arr[i]!=0) 
				return "false"; 
		
		return "true"; 
	} 
	return "false"; 
} 
	
int main() {

	string str1,str2; cin>>str1>>str2;
	cout<<is_permutation(str1,str2)<<endl;
	
	return 0;
}