algoadvance

Leetcode 242. Valid Anagram

Problem Statement

Given two strings s and t, write a function to determine if t is an anagram of s.

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.

Clarifying Questions

  1. Case Sensitivity: Are the strings case-sensitive?
    • Example: Is ‘Anagram’ considered the same as ‘anagram’?
    • Assumption: Yes, they are case-sensitive.
  2. Character Set: Are the strings limited to the alphabet, or can they contain any characters?
    • Assumption: They can contain any characters within the ASCII range.
  3. Input Constraints: What is the maximum length of the input strings?
    • Assumption: The length of strings can be up to (10^5).

Strategy

To determine if two strings are anagrams:

  1. Length Check: First, check if the lengths of the strings are different. If they are, they cannot be anagrams.
  2. Character Frequency Count: Use a hash map (or an integer array for ASCII characters) to count the frequency of each character in both strings.
  3. Comparison: Compare the frequency counts. If they match for all characters, the strings are anagrams.

Time Complexity

Let’s implement this in Java.

Code

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

public class Solution {
    public boolean isAnagram(String s, String t) {
        // If lengths are different, they cannot be anagrams
        if (s.length() != t.length()) {
            return false;
        }

        // HashMap to count frequency of each character
        Map<Character, Integer> charCountMap = new HashMap<>();

        // Count characters in string s
        for (char c : s.toCharArray()) {
            charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
        }

        // Reduce count based on string t
        for (char c : t.toCharArray()) {
            if (!charCountMap.containsKey(c)) {
                return false;
            }
            charCountMap.put(c, charCountMap.get(c) - 1);
            if (charCountMap.get(c) == 0) {
                charCountMap.remove(c);
            }
        }

        // If map is empty, all characters perfectly matched
        return charCountMap.isEmpty();
    }
}

Explanation

  1. Length Check: If the two strings have different lengths, return false.
  2. Character Frequency Count: Use a HashMap to store the frequency of each character in string s.
  3. Reduce Count for String t: Loop through string t and decrease the frequency count in the map. If a character is not found or its count goes negative, they are not anagrams.
  4. Final Check: If the hash map is empty at the end, it means all the characters matched perfectly in count and frequency, so return true. Otherwise, return false.

This solution ensures that we are checking both strings in linear time and using space proportional to the number of unique characters, making it efficient for large inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI