Check Permutation
You have been given two strings 'STR1' and 'STR2'. You have to check whether the two strings are anagram to each other or not.

Note:

Two strings are said to be anagram if they contain the same characters, irrespective of the order of the characters.

Example :

If 'STR1' = “listen” and 'STR2' = “silent” then the output will be 1. Both the strings contain the same set of characters.

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases. The first and only line of each test case contains two space-separated strings 'STR1' and 'STR2', respectively.

Output Format:

For each test case, return true if the two strings are anagrams of each other else return false. Print the output of each test case in a separate line.

Constraints:

1

Question

Check Permutation

You have been given two strings 'STR1' and 'STR2'. You have to check whether the two strings are anagram to each other or not.

Note:

Two strings are said to be anagram if they contain the same characters, irrespective of the order of the characters.

Example :

If 'STR1' = “listen” and 'STR2' = “silent” then the output will be 1.

Both the strings contain the same set of characters.

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases. 

The first and only line of each test case contains two space-separated strings 'STR1' and 'STR2', respectively.

Output Format:

For each test case, return true if the two strings are anagrams of each other else return false.

Print the output of each test case in a separate line.

Constraints:

1 <= T <= 100
1 <= |STR1|, |STR2| <= 10^3

Where |STR1| and |STR2| are the lengths of the string 'STR1' and 'STR2' respectively.

Time limit: 1 sec

Accepted Answer

Brute-Force

The basic idea of this approach is to sort both the strings and compare the characters of the sorted strings.

Sort both strings.
Compare the characters of the sorted strings.

Space Complexity: O(logn)Explanation:

O(1)

Since we not using any extra space, the overall space complexity will be O(1).

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), Where ‘N’ is the length of the strings.

Since we are sorting the strings which have time complexity O(N * log(N)).

Python (3.5)

"""
    Time complexity: O(N * log(N))
    Space complexity: O(1)

    Where 'N' is the length of the strings.
"""

def areAnagram(str1, str2):
    # Get lengths of both strings.
    n1 = len(str1)
    n2 = len(str2)

    # If length of both strings is not same, then they cannot be anagram.
    if (n1 != n2):
       return False

    # Sort both the strings.
    s1 = ""
    s2 = ""
    s1 = ''.join(sorted(str1))
    s2 = ''.join(sorted(str2))

    # Compare sorted strings.
    for i in range(n1):
        if (s1[i] != s2[i]):
            return False
        
    return True

Java (SE 1.8)

/*
    Time complexity: O(N * log(N))
    Space complexity: O(1)

    Where 'N' is the length of the strings.
*/

import java.util.Arrays;

public class Solution {
	public static boolean areAnagram(String str1, String str2) {
		// Get lengths of both strings.
		int n1 = str1.length();
		int n2 = str2.length();

		// If length of both strings is not same then they cannot be anagram.
		if (n1 != n2) {
			return false;
		}

		// Convert input string to char array.
		char tempArray1[] = str1.toCharArray();
		char tempArray2[] = str2.toCharArray();

		// Sort tempArray.
		Arrays.sort(tempArray1);
		Arrays.sort(tempArray2);

		// Compare sorted strings.
		for (int i = 0; i < n1; i++) {
			if (tempArray1[i] != tempArray2[i]) {
				return false;
			}
		}
		return true;
	}
}

C++ (g++ 5.4)

/*
    Time complexity: O(N * log(N))
    Space complexity: O(1)

    Where 'N' is the length of the strings.
*/

bool areAnagram(string &str1, string &str2){
    // Get lengths of both strings.
    int n1 = str1.length();
    int n2 = str2.length();

    // If length of both strings is not same, then they cannot be anagram.
    if (n1 != n2){
       return false;
    }

    // Sort both the strings.
    sort(str1.begin(), str1.end());
    sort(str2.begin(), str2.end());

    // Compare sorted strings.
    for (int i = 0; i < n1; i++){
        if (str1[i] != str2[i]){
            return false;
        }
    }
    return true;
}

Accepted Answer

Hashing

The idea is to create a ‘HASH’ array with all the values initialized to 0. We increment the value in the ‘HASH’ array for characters in 'STR1' and decrement for characters in ‘STR1’. Finally, if all ‘HASH’ array values are 0, then the two strings are anagram.

If lengths of ‘STR1’ and ‘STR2’ are not the same, return false.
Create a ‘HASH’ array with all values initialized to 0.
Start traversing ‘STR1’ and ‘STR2’ simultaneously.
Increment the value in the ‘HASH’ array for characters in ‘STR1’ and decrement the value in the ‘HASH’ array for characters in ‘STR2’.
If all values in the ‘HASH’ array are 0 after the above operations, then the two strings are anagram.

Space Complexity: OtherExplanation:

O(Number of different characters).

Since the size of the hash array will be equal to the number of different characters in the strings. Thus the space complexity will be O(Number of different characters).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the length of the strings.

Since we are using a Hash Array to store the frequency of characters. We are traversing the string once so the overall time complexity will be O(N).