Wednesday, 5 April 2017

C++ Program to check if two strings are permutation of each other in O(n) Time

This program checks if two strings are permutation of each other are not. I have used concept of hashing to determine if they are permutation of each other in O(n) time. Approach is simple we use two unordered map of type unordered_map <char,int> m1,m2. Char part of the map will work as a key whether int stores the count of the character which is working as a key in map. In our approach we simply traverse both the strings and put the occurrence of their each character in the map. Then we check if the length of the two strings are eqaul or not. If length of strings are not equal then string's can'b be permutation of each other, otherwise we will check the count of the every character of any string. If count of the every character is equal in both the srings then strings are permutation of each other otherwise not.

Time Complexity: O(n)

C++ Program to check if two strings are permutation of each other or not.
#include <iostream>
#include <unordered_map>
#include <stdio.h>
#include <string>
using namespace std;

int main()
{
    std::string s1;
    std::string s2;
    std::unordered_map <char,int> m1;
    std::unordered_map <char,int> m2;
    
    /* input string 1*/
    
    getline(cin,s1);
    for(int i=0;i<s1.length();i++)
    {
        m1[s1[i]]++;
    }
    
    /*input string 2*/
    
    getline(cin,s2);
    for(int i=0;i<s2.length();i++)
    {
        m2[s2[i]]++;
    }
    int flag=0;
    
    /*Compairing length of both strings */
    
    if(s1.length()!=s2.length())
    {
        flag=1;
    }
    else
    {
        /*checking occurrences of each character */
        
        for(int i=0;i<s2.length();i++)
        {
              char c=s1[i];  
              if(m1[c]!=m2[c])
              {
                  flag=1;
                  break;
              }
        }
    }
    if(flag==1)
    {
        printf("NO");
    }
    else
    {
        printf("YES");
    }
    return 0;
    
}

OUTPUT:

 


EmoticonEmoticon