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


  • 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


  • 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


  • 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


  • 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