Valid Anagram – LeetCode Solution in O(n) [Easy]

Problem

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.

LeetCode Problem Link

Input

String s and t

Output

true if t is an anagram of s, and false otherwise

Constraints

• 1 <= s.length, t.length <= 5 * 10⁴
• s and t consist of lowercase English letters.

Sample Input

s = "anagram", t = "nagaram"

Sample Output

true

Solution

Approach 1: Sorting (O(n*logn) solution)
A string t would be an anagram of string s if the number of each alphabet (a-z) in s is equal to t. For instance, if we have: s = “rat” and t = “tar”, we could sort the strings s and t. We’ll get string s = “art” and t = “art”. Now if we compare them, they would be same if both of them are anagrams and different otherwise.

Code Implementation

class Solution {
public:
    bool isAnagram(string s, string t) {
        int l1 = (int) s.size();
        int l2 = (int) t.size();

        if (l1 != l2) {
            return false;
        } else {
            sort(s.begin(), s.end());
            sort(t.begin(), t.end());

            if (!s.compare(t)) {
                return true;
            } else {
                return false;
            }
        }
        
    }
};

Time complexity: O(n*logn), where n is the max(s.length, t.length). O(n*logn) because of sort() method.

Approach 2: Hashmap (O(n) solution)
A string t would be an anagram of string s if the number of each alphabet (a-z) in s is equal to t. For instance, if we have: s = “rat” and t = “tar”. We could create two arrays (hashmaps) charS[26] and charT[26] such that charS[0] is the number of times char ‘a’ occur in string s and charT[0] is the number of times char ‘a’ occur in string t. After filling charS[] and charT[], we could compare them. Now, both charS[] and charT[] would be same if both of them are anagrams and different otherwise.

Code Implementation

class Solution {
public:
    
    void fillCharMap (int *a, string str) {
        int n = (int) str.size();

        for (int i=0; i<n; i++) {
            a[str[i] - 'a']++;
        }
    }

    bool isAnagram (string s, string t) {   
        const int MAX_SIZE = 26; 
        int charS[MAX_SIZE] = {0}, charT[MAX_SIZE] = {0};

        int l1 = (int) s.size();
        int l2 = (int) t.size();

        if (l1 != l2) {
            return false;
        } else {
            fillCharMap(charS, s);
            fillCharMap(charT, t);

            for (int i=0; i<MAX_SIZE; i++) {
                if (charS[i] != charT[i]) {
                    return false;
                }
            }

            return true;
        }
    }
};

Time complexity: O(n), where n is the max(s.length, t.length)