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