Learn to analyze and resolve the Anagrams problem by using Brute force, Sorting, Counting, and Histogramming algorithms

## Problem

• Given two strings s and t

• Write an algorithm to determine if t is an anagram of s

• Two strings are said to be anagrams of each other if the second string is formed by rearranging characters of the first string

## Example 1

• Input: s = "listen" and t = "silent"

• Output: true

## Example 2

• Input: s = "eleven plus two" and t = "twelve plus one"

• Expected output: true

## Example 3

• Input: s = "rat" and t = "car"

• Expected output: false

## Approach 1: Brute force

• Return false if two given strings s and t have different length

• Find all permutations of the first string

• Return true if any computed permutation equals the second string, otherwise, return false

public class AnagramsByBruteForce {
static boolean areAnagrams(String s, String t) {
if (s.length() != t.length()) {
return false;
}

return areAnagramsByBackTracking(0, s, t);
}

static boolean areAnagramsByBackTracking(int i, String s1, String s2) {
if (i == s1.length()-1) {
return s1.equals(s2);
}

for(int j=i; j<s1.length(); j++) {
s1 = swap(s1, i, j);

if (areAnagramsByBackTracking(i+1, s1, s2)) {
return true;
}

s1 = swap(s1, i, j); // backtracking
}

return false;
}

static String swap(String str, int i, int j) {
char[] arr = str.toCharArray();

char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

return String.valueOf(arr);
}

public static void main(String[] args) {
System.out.println(areAnagrams("listen", "silent"));
System.out.println(areAnagrams("rat", "car"));
}
}
• Output
true
false
• Time complexity: O(n!) as finding all permutations of a string of n characters costs O(n!) time

• Space complexity: O(1)

## Approach 2: Sorting

• Return false if two given strings s and t have different length

• Sort two given strings

• Compare the sorted strings, return true if they are equivalent, otherwise, return false

import java.util.Arrays;

public class AnagramsBySorting {
static boolean areAnagrams(String s, String t) {
if (s.length() != t.length()) {
return false;
}

char[] a1 = s.toCharArray();
char[] a2 = t.toCharArray();

Arrays.sort(a1);
Arrays.sort(a2);

return Arrays.equals(a1, a2);
}

public static void main(String[] args) {
System.out.println(areAnagrams("listen", "silent"));
System.out.println(areAnagrams("eleven plus two", "twelve plus one"));
System.out.println(areAnagrams("rat", "car"));
}
}
• Output
true
true
false
• Time complexity: O(nlogn) as sorting costs O(nlogn)

• Space complexity: O(n) as two arrays of size n are used

## Approach 3: Counting

• Return false if two given strings s and t have different length

• Count and compare occurrences of 'a' to 'z' character in s and t, return false immediately if any comparison is different

public class AnagramsByCounting {
static boolean areAnagrams(String s, String t) {
if (s.length() != t.length()) {
return false;
}

for (char ch = 'a'; ch <= 'z'; ch++) {
if (countOccurrences(ch, s) != countOccurrences(ch, t)) {
return false;
}
}

return true;
}

static int countOccurrences(char c, String s) {
return s.length() - s.replace(String.valueOf(c), "").length();
}

public static void main(String[] args) {
System.out.println(areAnagrams("listen", "silent"));
System.out.println(areAnagrams("eleven plus two", "twelve plus one"));
System.out.println(areAnagrams("rat", "car"));
}
}
• Output
true
true
false
• Time complexity: O(n) as string replacement costs O(n)

• Space complexity: O(1)

## Approach 4: Histogramming

• Return false if two given strings s and t have different length

• Use a HashMap to build a histogram for all characters in s and t. We don't need 2 histograms, we can increase value on s and decrease value on t. If there is any value different than 0 in the final histogram, we can conclude that s and t are not anagrams

public class AnagramsByHistogramming {
static boolean areAnagrams(String s, String t) {
if (s.length() != t.length()) {
return false;
}

Map<Character, Integer> histogram = new HashMap<>();

for (int i = 0; i < s.length(); i++) {
histogram.compute(s.charAt(i), (k,v) -> (v == null ? 0 : v) + 1);
histogram.compute(t.charAt(i), (k,v) -> (v == null ? 0 : v) - 1);
}

for (int count : histogram.values()) {
if (count != 0) {
return false;
}
}

return true;
}

public static void main(String[] args) {
System.out.println(areAnagrams("listen", "silent"));
System.out.println(areAnagrams("eleven plus two", "twelve plus one"));
System.out.println(areAnagrams("rat", "car"));
}
}
• Output
true
true
false
• Time complexity: O(n) as the iteration costs O(n)

• Space complexity: O(n) as a hashmap of size n is used