Valid Anagram easy

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

Steps to Solve:

1. Check for Length: If the lengths of s and t are different, they cannot be anagrams, so return false.

2. Character Frequency Counting: Create a hash map (or an array if you know the character set is limited, like only lowercase English letters) to store the frequency of each character in string s.

3. Compare Frequencies: Iterate through string t. For each character in t, check if it exists as a key in the hash map. If it does, decrement its frequency; otherwise, it's not an anagram, so return false.

4. Check for Zero Frequencies: After iterating through t, check if all frequencies in the hash map are zero. If they are, it means all characters in t were present in s with the same frequencies, making them anagrams; return true. Otherwise, return false.

Explanation:

The solution leverages the fact that anagrams have the same character frequencies. By counting the character frequencies in s and then checking if t has the same frequencies, we efficiently determine if they are anagrams. Using a hash map allows us to handle any character set without limitations. An array is a more space-efficient option if we know the character set beforehand (e.g., lowercase English alphabet).

Code (C++):

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }

    unordered_map<char, int> charCount;
    for (char c : s) {
        charCount[c]++;
    }

    for (char c : t) {
        if (charCount.find(c) == charCount.end() || charCount[c] == 0) {
            return false;
        }
        charCount[c]--;
    }

    return true;
}

int main() {
    string s1 = "anagram";
    string t1 = "nagaram";
    cout << "Is \"" << s1 << "\" an anagram of \"" << t1 << "\"? " << (isAnagram(s1, t1) ? "true" : "false") << endl; // Output: true

    string s2 = "rat";
    string t2 = "car";
    cout << "Is \"" << s2 << "\" an anagram of \"" << t2 << "\"? " << (isAnagram(s2, t2) ? "true" : "false") << endl; // Output: false

    return 0;
}

Complexity:

• Time Complexity: O(m + n), where m and n are the lengths of strings s and t respectively. We iterate through each string once.
• Space Complexity: O(min(m, n)) in the worst case. The hash map (or array) will store at most the number of unique characters in the smaller string. In the best case it's O(1) if the strings are very short or have few unique characters.