Valid Anagrams

Practice here

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

Brute Force: Sorting#

Two strings are anagrams if and only if they contain exactly the same characters with the same frequencies. Sorting both strings brings identical characters together, so a simple string equality check is sufficient after sorting. The trade-off is O(n log n) time from sorting versus the O(n) possible with frequency counting, but no extra space beyond the in-place sort is needed.

class Solution {
public:
    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;
    }
};

Time Complexity: O(nlogn)

Space Complexity: O(1)

Better Approach: Hash Map#

Build a frequency map by incrementing counts for every character in s, then decrement for each character in t. If at any point a character in t is not in the map or its count drops below zero, t uses a character more times than s does, so it cannot be an anagram. This achieves O(n) time at the cost of O(n) space for the hash map, making it faster than sorting but with higher space usage.

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

        unordered_map<char, int> freqMap;

        for(char c: s)
            freqMap[c]++;

        for(char c: t){
            if(!freqMap.count(c) || --freqMap[c]<0)
                return false;
        }

        return true;

    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Better Approach: For fixed characters#

When the alphabet is fixed (26 lowercase letters), a fixed-size array of 26 integers replaces the hash map. Incrementing for characters in s and decrementing for characters in t is the same logic as the hash map approach, but the array has O(1) lookup and constant 26-element space regardless of input size. This is the optimal solution: O(n) time and effectively O(1) space, making it strictly better than both sorting and the general hash map approach.

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

        vector<int> freqList(26, 0);

        for(char c: s)
            freqList[c-'a']++;

        for(char c: t){
            if(--freqList[c-'a']<0)
                return false;
        }

        return true;

    }
};

Time Complexity: O(n)

Space Complexity: O(1)