Anagram or Not (IMAGE NOT ADDED)

Concepts Used

Strings, Hashing

Difficulty Level

Easy

Problem Statement (Simplified):

Check if string B can be achieved by A by rearranging letters of A. If yes print YES else NO;

See original problem statement here

Test Case

Input:
1
prep
perp

Output:
YES

Explanation:
We can achieve string B from string A if we rearrange 'r', 'e' and 'p' in string A. All possible arrangements for 'prep' are :

prep
rpep
eprp
perp
repp
erpp
pper
eppr
pepr
rppe
prpe
ppre

As we can see 'pepr' is in these arrangements. So they are anagram to each other.

Solving Approach :

Bruteforce Approach:

1) It can be solved by rearranging all letters of A and then checking all permutations, if any permutation is the same as B, then print YES, else if no permutation is same, we print NO. But this is not an efficient solution as it will take $O(n!)$ time complexity to check all permutations where $n$ is the length of the string.
2) Can you see, the above approach takes longer times for longer strings, but this can be solved more efficiently. Can you guess? Let's see a more efficient approach.

Efficient Approach :

  • As we saw in the last approach, it was very inefficient, we can refer some websites to learn programming and use Hashing to solve this problem more efficiently.
    Hashing: This method uses a hash table that stores each character of alphabets as an index and corresponding value related to character, in our case it stores the number of times a character appears in a string.

1) For two strings to be an anagram, they need to follow two conditions that are :
> 1) They must be of equal length.
> 2) They must have the same characters appearing the same number of times in any order.
2) We can check for condition $2$ which provides a more efficient solution to us.
3) To keep count of character's appearance, we use a hash table of size 26, where index 0 to 26 refer to letters in alphabets i.e. a to z.
3) To get the index value of any character S[i] we subtract a from it, hence the resultant provides a valid index.
4) When we decrease a from any character, it substracts 97(a's ASCII Value) from it's ASCII Value giving it's valued between 0 and 26, for example, b has ASCII value 97, when we subtract a from it, it results in 1. Hence, index 1 will store the number of appearances of b.
5) So we count appearances of the character in both string and match them if all are found the same, that means they're anagram, else they are not.

Example

  • Lets assume string A be $prep$ and string B be $pepr$.

  • Initially our hash table h have 0 at all places.

  • For every character we read, it's the corresponding index in the hash table can be achieved by using the following formula :

$index = ASCII(c) - ASCII('a')$ where $c$ is current character.

  • For example, for character $p$ it's corresponding index will be $ASCII('p')-ASCII('a')$ i.e. $112 - 97 = 15$. So at every appearance of character $p$, we'll increase value at index $15$ by 1.

  • So after counting, our hash tables (with corresponding index and character) becomes,

Graphic-1 Here

where $hA$ stores appearances of characters in string $A$, while $hB$ stores appearances of characters in string $B$.

  • After we have counted all appearances in string A and string B, we check if all characters appear the same number of time or not.

  • If all characters appear same number of time in both strings, both strings are $Anagram$ else they are not.

  • As we can see in the above figure, all characters have same values at same indexes in hash tables, hence they're $Anagram$.

Solutions

#include <stdio.h>

    int main()
    {
      int test;
      scanf("%d",&test);

      while(test--){

        char a[10001], b[10001];
        scanf("%s%s", a,b);
        int anagram = 1;

        if(strlen(a) != strlen(b))
            anagram = 0;
        else{
            int hash[26] = {0};
            for(int i = 0; i<strlen(a); i++){
              hash[a[i]-'a']++;
              hash[b[i]-'a']--;
        }
        for(int i=0; i<26; i++){
          if(hash[i]!=0)
            anagram = 0; 
        }}

        if(anagram)
          printf("YES\n");
        else
          printf("NO\n");

      }
      return 0;
    }

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

    int main()
    {
      int test;
      cin>>test;

      while(test--){

        char a[10001], b[10001];
        cin>>a>>b;
        int anagram = 1;

        if(strlen(a) != strlen(b))
            anagram = 0;
        else{
            int hash[26] = {0};
            for(int i = 0; i<strlen(a); i++){
              hash[a[i]-'a']++;
              hash[b[i]-'a']--;
        }
        for(int i=0; i<26; i++){
          if(hash[i]!=0)
            anagram = 0; 
        }}

        if(anagram)
          cout<<"YES\n";
        else
          cout<<"NO\n";

      }
      return 0;
    }


import java.util.*;
    import java.io.*;
    import java.lang.Math;

    public class Main {
      public static void main(String args[]) throws IOException {

        Scanner sc= new Scanner(System.in);
        int test = sc.nextInt();
          while(test != 0){

            String a = sc.next();
            String b= sc.next();
            int anagram = 1;

            if(a.length() != b.length())
                anagram = 0;
            else{
                int hash[] = new int[26];
                for(int i = 0; i<a.length(); i++){
                  hash[a.charAt(i)-'a']++;
                  hash[b.charAt(i)-'a']--;
            }
            for(int i=0; i<26; i++){
              if(hash[i]!=0)
                anagram = 0; 
            }}

            if(anagram == 1)
              System.out.println("YES");
            else
              System.out.println("NO");
            test--;
          }

      }
    }

Space Complexity of this approach would be O(1)

Previous post Aman and Math
Next post Get the Sun Light

Leave a Reply

Your email address will not be published. Required fields are marked *