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

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

2. Character Frequency Counting: Create a HashMap (or array if you know the character set is limited like only lowercase English letters) to store the frequency of each character in string s. Iterate through s and increment the count for each character.

3. Compare Frequencies: Iterate through string t. For each character in t, decrement its count in the HashMap. If the count becomes negative at any point, it means t has more occurrences of that character than s, so they can't be anagrams – return false.

4. Final Check: After iterating through t, if all counts in the HashMap are zero, it means the character frequencies in s and t are identical, therefore they are anagrams, and we return true. Otherwise (if any count remains non-zero), they are not anagrams, and we return false.

Explanation

The core idea is to check if the character frequencies are the same in both strings. Using a HashMap allows us to efficiently count character frequencies. The algorithm avoids sorting, which would have a higher time complexity. Decrementing the counts in the HashMap as we iterate through the second string directly confirms if each character in the second string has a matching counterpart in the first.

Code

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Integer> charCount = new HashMap<>();

        // Count character frequencies in s
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        // Decrement counts for characters in t
        for (char c : t.toCharArray()) {
            if (!charCount.containsKey(c) || charCount.get(c) == 0) {
                return false; // Character not found or count already zero
            }
            charCount.put(c, charCount.get(c) - 1);
        }

        // Check if all counts are zero
        for (int count : charCount.values()) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the strings. We iterate through the strings once each. HashMap operations (get, put) are typically O(1) on average.

• Space Complexity: O(1) in the case of only lowercase English letters (using an array to store frequencies). If the character set is unlimited, it becomes O(n) in the worst case (using a HashMap). In practice, the space used by the HashMap is often relatively small compared to the input string lengths.