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:

It can be solved by rearranging all letters of
A
and then checking all permutations, if any permutation is the same asB
, then printYes
, else if no permutation is same, we printNo
. 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. 
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.
 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.
 We can check for condition 2 which provides a more efficient solution to us.
 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
toz
.  To get the index value of any character
S[i]
we subtracta
from it, hence the resultant provides a valid index.  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 subtracta
from it, it results in 1. Hence, index 1 will store the number of appearances ofb
.  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 stringB
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,
Graphic1 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 stringB
, 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
#includeint 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
#includeusing 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")
Space Complexity of this approach would be
O(1)
[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