Anagram or Not

Last Updated on April 6, 2022 by Ria Pathak

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 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 :
   • They must be of equal length.
   • 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.
4. To get the index value of any character S[i] we subtract a from it, hence the resultant provides a valid index.
5. 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.
6. 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 

    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

						 

#include 
    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

						 

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

						 

for _ in range(int(input())):
	
	a = input()
	b = input()
	anagram = 1

	if len(a) != len(b):
		
		anagram = 0
	else:

		hash = [0] * 26

		for i in range(len(a)):

			hash[ord(a[i]) - ord("a")] += 1
			hash[ord(b[i]) - ord("a")] -= 1

		for i in range(26):

			if hash[i] != 0:
				anagram = 0

	if anagram:
		print("YES")

	else:
		print("NO")

[forminator_quiz id="758"]

This article tried to discuss the concepts of Strings, Hashing. Hope this blog helps you understand and solve the problem. To practice more problems on Strings, Hashing you can check out MYCODE | Competitive Programming