#### 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
to solve this problem more efficiently.Hashing

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 Herewhere $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)`