Valid Anagram – 242. Leetcode

An anagram is a word or phrase formed by rearranging the letters of another word or phrase. For example, “listen” and “silent” are anagrams. This problem asks you to determine if two given strings are anagrams of each other, but it should also work with Unicode characters like emojis or symbols.

Brute Force Approach

Idea:

The brute force approach involves sorting both strings and comparing the sorted versions. If they are equal, the strings are anagrams.

import java.util.Arrays;

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

        // Convert strings to character arrays and sort them
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        Arrays.sort(sArray);
        Arrays.sort(tArray);

        // Compare sorted arrays
        return Arrays.equals(sArray, tArray);
    }
}

The strings are converted into character arrays, sorted, and then compared. Sorting ensures that the characters are arranged in the same order if the strings are anagrams. This approach has a time complexity of O(n log n) due to sorting and a space complexity of O(n) for storing the sorted arrays.

Optimal Algorithm and Data Structure

Algorithm: Character Frequency Count

Data Structure: Hash Map

Why it works:

A hash map is used to count the frequency of each character in one string and then decrement the counts for the other string. If all counts are zero at the end, the strings are anagrams.

Characteristics of the Problem:

• You need to compare two sets of characters, allowing for duplicates.

• The input can contain Unicode characters, which means a fixed array (like for ASCII) cannot be used.

• Efficient comparison of character frequencies is required.

Why it’s Better Than Brute Force:

• Brute Force: Sorting takes O(n log n) and additional space for character arrays.

• Hash Map Approach: Counting characters is linear (O(n)), and space is used efficiently for only unique characters.

Steps of the Algorithm

1. If the strings have different lengths, return false.

2. Create a hash map to count character frequencies in the first string.

3. Iterate through the second string, decrementing the character counts in the hash map.

4. If any character count becomes negative or the map contains leftover characters, return false.

5. If all counts are zero, return true.

import java.util.HashMap;

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

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

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

        // Decrease character counts based on the second string
        for (char c : t.toCharArray()) {
            if (!charCount.containsKey(c)) {
                return false; // Character not found
            }
            charCount.put(c, charCount.get(c) - 1);
            if (charCount.get(c) < 0) {
                return false; // Too many occurrences
            }
        }

        // All counts should be zero
        for (int count : charCount.values()) {
            if (count != 0) return false;
        }

        return true;
    }
}

Step-by-Step Explanation

1. Initialize HashMap

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

• Creates a HashMap to store the frequency of each character in the first string.
• This data structure helps keep track of how many times each character appears in s, allowing efficient lookups and updates.

2. Count Characters in s

for (char c : s.toCharArray()) {
    charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}

• Iterate through each character in s:
  • If the character already exists in the HashMap, it increments its counts.
  • If it doesn’t exist, it initializes the count to 1
• Why? This step build the frequency map for s, which is later used to verify it t has matching frequencies.

3. Adjust Counts for Characters in t

for (char c : t.toCharArray()) {
    if (!charCount.containsKey(c)) {
        return false; // Character not found
    }
    charCount.put(c, charCount.get(c) - 1);
    if (charCount.get(c) < 0) {
        return false; // Too many occurrences
    }
}

• Iterates through each character in t.
• Checks if the characters exists in the HashMap
  • If it doesn’t, it means t has a character not present in s, so it returns false.
• Decrements the count of the character in the map
  • If count becomes negative, it means t has more occurrences of that character than s, so it returns false.

4. Final Check for Zero Counts

for (int count : charCount.values()) {
    if (count != 0) return false;
}

• Iterates through the values (frequencies) in the HashMap and checks if any are not zero.
• If all characters in s and t matched perfectly, the counts in the map should now all be zero.

Key Takeaways

• Efficiency: Hash maps are ideal for frequency counting with Unicode characters, providing O(1) access and modification.

• Space Complexity: Hash maps are efficient in space, using memory proportional to the number of unique characters.

• Algorithmic Pattern: The problem follows a frequency counter pattern, which is effective for comparison-based problems where order doesn’t matter.