Anagrams Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/anagrams

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two strings A and B, find whether A and B are anagrams of each other or not.

Naive Approach

The naive approach involves the observation that if A and B are anagrams, then some permutation of A will be equal to B. Also note that if the lengths of the strings are different, they can never be anagrams of each other. So we can generate all permutations of A and check if any of them is equal to B or not.

Analysis

• Time Complexity: O(n * n!) // Length of the strings
• Space Complexity: O(1)

Implementation

C++

bool areAnagrams(string A, string B) {
    if(A.length() != B.length()) {
		return false;
	}
	sort(A.begin(), A.end());
	do {
		if(A == B) {
			return true;
		}
	} while(next_permutation(A.begin(), A.end()));
	return false;
}

Java

class Solution {
	void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	void reverse(int[] arr, int start, int end) {
		int left = start, right = end;
		while(left < right) {
			swap(arr, left, right);
			left++;
			right--;
		}
	}
	boolean is_sorted(int[] arr) {
		boolean sorted = true;
		for(int i = 1; i < arr.length; i++) {
			if(arr[i] < arr[i - 1]) {
				sorted = false;
			}
		}
		return sorted;
	}
	int nextGreaterPermutation (int[] arr) {
		reverse(arr, 0, arr.length - 1);
        if (is_sorted(arr) == true) {
            return -1;
		}
        int index = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] > arr[i]) {
                index = i;
                break;
            }
        }
        for (int i = 0; i < index; i++) {
            if (arr[i] > arr[index]) {
                swap(arr, i, index);
                break;
            }
        }
        reverse(arr, 0, index - 1);
        reverse(arr, 0, arr.length - 1);
		return 1;
	}
	boolean areAnagrams(String A, String B) {
		if(A.length() != B.length()) {
			return false;
		}
	    int permuteA[] = new int[A.length()];
		int permuteB[] = new int[A.length()];
		for (int i = 0; i < A.length(); i++) {
			permuteA[i] = A.charAt(i) - 'a';
			permuteB[i] = B.charAt(i) - 'a';
		}
		Arrays.sort(permuteA);
		while (nextGreaterPermutation(permuteA) != -1) {
			boolean ok = true;
			for (int i = 0; i < A.length(); i++) {
				if(permuteA[i] != permuteB[i]) {
					ok = false;
					break;
				}
			}
			if(ok) {
				return true;
			}
			continue;
		}
		return false;
	}
}

Optimal Approach

Observe that in words that are anagrams are basically permutations of each other. So, the frequency of each character in each word should be equal. We can obtain this by hashing the frequency of the characters with a hash array, and checking if the frequency of each character is equal in both the words.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) // 26 alphabets only

Implementation

C++

bool areAnagrams(string A, string B) {
    if(A.length() != B.length()) {
			return false;
		}
	    int hashA[26] = {0}, hashB[26] = {0};
		for (int i = 0; i < A.length(); i++) {
			hashA[A[i] - 'a']++;
			hashB[B[i] - 'a']++;
		}
		for (int i = 0; i < 26; i++) {
			if(hashA[i] != hashB[i]) {
				return false;
			}
		}
		return true;
}

Java

class Solution {
	boolean areAnagrams(String A, String B) {
		if(A.length() != B.length()) {
			return false;
		}
	    int hashA[] = new int[26];
		int hashB[] = new int[26];
		for(int i = 0; i < A.length(); i++) {
			hashA[A.charAt(i) - 'a']++;
			hashB[B.charAt(i) - 'a']++;
		}
		for(int i = 0; i < 26; i++) {
			if(hashA[i] != hashB[i]) {
				return false;
			}
		}
		return true;
	}
}