Practice Link

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, using all the original letters exactly once.

Brute Force#

Sort both strings and compare them character by character. Two strings are anagrams if and only if their sorted forms are identical. Sorting takes O(n log n) but no extra data structures are needed.

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    
    return s == t;
}

Time Complexity: O(nlogn), (where n-> size of strings)

Space Complexity: O(1)

One Hash Map#

Count the frequency of each character in s using a single hash map. Then walk through t, decrementing each character's count and removing the entry when it hits 0 (tracking how many distinct characters remain). If the map is fully emptied after processing t, the strings are anagrams. One map and two linear scans gives O(n) time. The map size is bounded by the alphabet (26 or 256 characters), so space is effectively O(1).

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size())
            return false;

        

        unordered_map<char,int> hashMap;
        for(auto c: s)
            hashMap[c] += 1;

        int sz = hashMap.size();
        for(auto c: t)
        {
            hashMap[c]--;
            if(hashMap[c]==0)
                sz--;
        }
        return sz==0;
    }
};

Time Complexity: O(n), (where n-> size of strings)

Space Complexity: O(1)

Two Hashmaps#

Build separate frequency maps for s and t simultaneously in a single pass. Then compare the two maps for equality. This is simpler to reason about than the one-map approach but uses twice the memory. Both approaches are O(n) time and O(1) space (alphabet-bounded maps).

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()){
            return false;
        }
        int n = s.length();

        unordered_map<int,int> counts;
        unordered_map<int,int> countt;
        for(int i=0;i<n;i++){
            counts[s[i]]++;
            countt[t[i]]++;
        }
        return counts == countt; 
    }
};

Selecting Approach#