Anagram Pairs

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
58 upvotes
Asked in companies
CiscoThought WorksInfosys

Problem statement

You are given two strings 'str1' and 'str1'.


You have to tell whether these strings form an anagram pair or not.


The strings form an anagram pair if the letters of one string can be rearranged to form another string.

Pre-requisites:

Anagrams are defined as words or names that can be formed by rearranging the letters of another word. Such as "spar" can be formed by rearranging letters of "rasp". Hence, "spar" and "rasp" are anagrams. 

Other examples include:

'triangle' and 'integral'
'listen' and 'silent'
Note:
Since it is a binary problem, there is no partial marking. Marks will only be awarded if you get all the test cases correct. 
Detailed explanation ( Input/output format, Notes, Images )
Input format:
The first and the only line of input contains two single space-separated strings Str1 and Str2, respectively.
Output format:
The only line of output contains either True or False. True, if the given two strings form an anagram pair and False otherwise.

You don't have to explicitly print by yourself. It has already been taken care of.
Remember/Consider:
Neither of the two input strings contains spaces in between, except to differentiate one from the other.

Also, both the strings will be in lowercase characters.   
Sample Input 1:
rasp spar
Sample Output 1:
True
Explanation For Sample Output 1:
Since both the strings have one 'a', one 'p', one 'r', and one 's', they are anagrams.
Sample Input 2:
rasp spaz
Sample Output 2:
False
Constraints:
1 <= N <= 10^5 
1 <= M <= 10^5
Where N and M are the lengths of the strings str1 and str2 , respectively.

Time Limit: 1sec
Follow Up:
Can you solve this in O( N ) time?
Hint

Is there a specific property of anagrams that can come in handy? Something that is related to the number/count of characters?

Approaches (2)
Count Characters

Anagrams have a unique property: the counts of each distinct character present in both strings are the same. One way to check this is: 

  1. Sort both strings, so that all the same characters come together
  2. Then loop through both strings together and check each element in both strings one by one
  3. If at any position, the characters are found to be different or if the lengths of the two strings are different, they cannot be anagrams
  4. Otherwise, they will be anagrams
Time Complexity

O(N * log(N) + (M * log(M))), where N and M are the lengths of the two input strings.

 

Since we are sorting the strings, the time complexity will be O(N * log(N) + (M * log(M))).

Space Complexity

O(1).

 

Constant space is used.

Code Solution
(100% EXP penalty)
Anagram Pairs
Full screen
Console