Valid Anagram

Problem Statement

Given two strings, s and t, the task is to determine whether the string t is an anagram of string s. An anagram is characterized as a rearrangement of the letters of one string to form another. Therefore, if t can rearrange its letters to match exactly the letters and their counts in s, the function should return true. If not, it returns false.

Examples

Example 1

Input:

s = "anagram", t = "nagaram"

Output:

true

Example 2

Input:

s = "rat", t = "car"

Output:

false

Constraints

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

Approach and Intuition

The problem is essentially about checking if two strings have the identical character counts for each type of letter, making them anagrams of each other. Here's the approach based on the example problems and constraints provided:

1. If the lengths of s and t are different, immediately return false because two strings of different lengths cannot be anagrams.
2. Count the frequency of each letter in both s and t.
3. Compare the frequency counts:
   • If they match for every letter, return true.
   • If there's a discrepancy in counts for any letter, return false.

Example walk-through based on provided examples:

• For s = "anagram" and t = "nagaram", both strings sort to "aaagmnr", hence they are anagrams of each other, which means the returned value is true.
• For s = "rat" and t = "car", sorting them gives "art" and "acr" respectively, which aren't identical, making them not anagrams, so the return value is false.

Note that both strings consist of only lowercase English letters, and this uniformity simplifies the approach since we do not need to handle cases for uppercase letters or other characters. The check process scales with the maximum possible lengths of s and t, up to 50,000 characters, so an efficient counting method is crucial for performance.

Solutions

public boolean checkAnagram(String str1, String str2) {
    if (str1.length() != str2.length()) {
        return false;
    }
    int[] count = new int[26];
    for (int i = 0; i < str1.length(); i++) {
        count[str1.charAt(i) - 'a']++;
    }
    for (int i = 0; i < str2.length(); i++) {
        count[str2.charAt(i) - 'a']--;
        if (count[str2.charAt(i) - 'a'] < 0) {
            return false;
        }
    }
    return true;
}