# Anagram or Not (IMAGE NOT ADDED)

Strings, Hashing

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, b;
scanf("%s%s", a,b);
int anagram = 1;

if(strlen(a) != strlen(b))
anagram = 0;
else{
int hash = {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, b;
cin>>a>>b;
int anagram = 1;

if(strlen(a) != strlen(b))
anagram = 0;
else{
int hash = {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;
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)`