Anagram Pairs
Pre-requisites: Anagrams are defined as words or names that can be formed by rearranging 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'

Now, Coding Ninjas has the following task for you:

You would be given two strings. 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.

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.

Input format:

The first and the only line of input contains two single space-separated strings Str1 and Str2, respectively.

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.

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.

Constraints:

1

Question

Anagram Pairs

Pre-requisites: Anagrams are defined as words or names that can be formed by rearranging 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'

Now, Coding Ninjas has the following task for you:

You would be given two strings. 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.

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.

Input format:

The first and the only line of input contains two single space-separated strings Str1 and Str2, respectively.

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.

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.

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

Accepted Answer

Approach :

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.

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

Accepted Answer

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:

Sort both strings, so that all the same characters come together
Then loop through both strings together and check each element in both strings one by one
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
Otherwise, they will be anagrams

Space Complexity: O(1)Explanation:

O(1).

Constant space is used.

Time Complexity: O(1)Explanation:

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))).

Accepted Answer

Frequency Array Approach

Create a 26 sized array. Each element A[i] of the array stores the difference of the frequencies of the (i + 1)th alphabet in the strings.
At i=0, frequency of ‘a’ is stored because it is the first character.
For example, if A[2] is -2, that means:

Frequency of ‘c’ in first string - Frequency of ‘c’ in second string = -2

2. To create this array, first initialize an array of size 26 and fill it with zeros.

3. Iterate through the characters of the first string and increase the element at the corresponding location by 1. For example if the current character is denoted by ‘c’ and the array by arr, then you’ll do arr['c' - ‘a’] += 1. This works because all characters are lowercase.

4. Then repeat the previous step for the second array but this time, decrease the element at the corresponding location by 1

5. Now iterate through the array and see if all elements in it are zero. If any one element is non zero, then the strings are not anagrams. Otherwise, they are anagrams

Space Complexity: O(1)Explanation:

O(26).

Since we are using an array of constant size, the space complexity will be O(26).

Time Complexity: O(1)Explanation:

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

Since we are iterating over the strings, the time complexity will be O(N + M).