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. Feel free to share your thought about my content.

What is your approach? The problem was picked from leetcode.com. You can submit your solution in any programming language and check the performance.