Problem statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1

Input: s = "anagram", t = "nagaram"
Output: true

Example 2

Input: s = "rat", t = "car"
Output: false

Constraints

• 1 <= s.length, t.length <= 5 * 10^4.

• s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Solution 1: Rearrange both s and t into a sorted string

Code

#include <iostream>
#include <algorithm>
using namespace std;
bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    return s == t;
}
int main() {
    cout << isAnagram("anagram", "nagaram") << endl;
    cout << isAnagram("rat", "car") << endl;
}

Output:
1
0

Complexity

• Runtime: O(NlogN), where N = s.length.

• Extra space: O(1).

Solution 2: Count the appearances of each letter

Code

#include <iostream>
using namespace std;
bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    int alphabet[26];
    for (int i = 0; i < 26; i++) {
        alphabet[i] = 0;
    }
    for (char& c : s) {
        alphabet[c - 'a']++;
    }
    for (char& c : t) {
        alphabet[c - 'a']--;
        if (alphabet[c - 'a'] < 0) {
            return false;
        }
    }
    return true;    
}
int main() {
    cout << isAnagram("anagram", "nagaram") << endl;
    cout << isAnagram("rat", "car") << endl;
}

Output:
1
0

Complexity

• Runtime: O(N), where N = s.length.

• Extra space: O(1).

Solution 3: If the inputs contain Unicode characters

In the solutions above, the array alphabet represents 26 letters 'a' to 'z'. You can generalize to allow it contains any character by using a map.

Code

#include <iostream>
#include <unordered_map>
using namespace std;
bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    unordered_map<char, int> alphabet;
    for (char& c : s) {
        alphabet[c]++;
    }
    for (char& c : t) {
        alphabet[c]--;
        if (alphabet[c] < 0) {
            return false;
        }
    }
    return true;    
}
int main() {
    cout << isAnagram("anagæam", "nagaæam") << endl;
    cout << isAnagram("rat", "car") << endl;
}

Output:
1
0

Complexity

• Runtime: O(N), where N = s.length.

• Extra space: O(1).

---

Key takeaway

• An array of 26 integers can represent the English alphabet.

• Counting the appearances can help identify if a word is a permutation of another.

• You can use a map to count the appearances of the letters of a word.

---

Thanks for reading! Get my book "10 Classic Coding Challenges" for FREE.