HelloKoding

Practical coding guides

Detect Anagrams

In this article, you will learn to analyze and resolve the Anagrams Detection 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 one another 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

AnagramsByBruteForce.java

package com.hellokoding.algorithm;

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

AnagramsBySorting.java

package com.hellokoding.algorithm;

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

AnagramsByCounting.java

package com.hellokoding.algorithm;

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
  • Build a frequency histogram of characters in each string and checking whether those histograms are the same

AnagramsByHistogramming.java

package com.hellokoding.algorithm;

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

        s = s.replaceAll("\\s", "");
        t = t.replaceAll("\\s", "");

        int[] frequencies = new int[26];

        for (int i = 0; i < s.length(); i++) {
            frequencies[s.charAt(i) - 'a']++;
            frequencies[t.charAt(i) - 'a']--;
        }

        for (int count : frequencies) {
            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 an array of size n is used
Follow HelloKoding