Introduction & Problem Explanation

The Valid Anagram problem asks us to determine if two given strings, s and t, are anagrams of each other.

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. For example, s = "anagram" and t = "nagaram" are anagrams because they have the exact same character frequencies. On the other hand, s = "rat" and t = "car" are not anagrams. Identifying matches like this is a core technique in search indexing, text parsing, and cryptography.

Illustration of Valid Anagram checking character frequencies in Java
Real-World Analogy: The Scrabble Letter Checker

Imagine you are playing Scrabble. You are given a tray containing a set of letter tiles spelling "listen". A friend challenges you to check if another word, "silent", can be made using exactly the same tiles. To verify this, you count the quantity of each letter tile in "listen" (e.g., 1 'l', 1 'i', 1 's', 1 't', 1 'e', 1 'n') and write them down. Then, you look at "silent" and subtract the letters one by one from your list. If you end up with exactly zero counts for all letters, you have verified that they are perfect anagrams! If you are short of a letter or have any tiles left over, they are not anagrams.

The Algorithmic Approach

1. The Sorting Approach (O(n log n) Time, O(n) Space)

If we sort the characters of both strings alphabetically, any two anagrams will yield identical sorted strings. We can simply convert the strings to char arrays, sort them, and check if they are equal. While simple, this takes O(n log n) time due to sorting, which is less than optimal for long strings.

2. The Frequency Counting Approach (O(n) Time, O(1) Space)

Since the input strings consist only of lowercase English alphabets, we can count the frequency of each character using an integer array of size 26. We iterate through the strings: incrementing the count for characters in s and decrementing the count for characters in t. If the two strings are anagrams, every single slot in the frequency array must balance out to exactly 0. This runs in optimal O(n) linear time.

Step-by-Step Execution Walkthrough

Let's trace the frequency counting algorithm on strings s = "anagram" and t = "nagaram":

  1. Step 1 (Length Check): We check if s.length() != t.length(). Both are length 7. We proceed.
  2. Step 2 (Initialization): We create an integer array of size 26 to store character counts: count = [0, 0, ..., 0].
  3. Step 3 (Iteration i = 0):
    • Character in s is 'a'. We increment: count['a' - 'a'] = count[0]++ → count[0] = 1.
    • Character in t is 'n'. We decrement: count['n' - 'a'] = count[13]-- → count[13] = -1.
  4. Step 4 (Iteration i = 1):
    • Character in s is 'n'. We increment: count[13]++ → count[13] = 0.
    • Character in t is 'a'. We decrement: count[0]-- → count[0] = 0.
  5. Step 5 (Iteration i = 2):
    • Character in s is 'a'. Increment count[0] to 1.
    • Character in t is 'g'. Decrement count[6] to -1.
  6. Step 6 (Trace continues): We repeat this for all remaining characters. At the end of the loop, the incrementing from s and decrementing from t completely balance out.
  7. Step 7 (Final Check): We check if all elements in the count array are 0. Since they are all 0, the method returns true.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • if (s.length() != t.length()) return false;: An immediate check. Strings of different lengths can never be anagrams.
  • count[s.charAt(i) - 'a']++ and count[t.charAt(i) - 'a']--: Using the ASCII offset -'a' maps the characters 'a'-'z' to array indices 0-25, allowing fast operations.
  • if (i != 0) return false;: Ensures that the letter frequencies balance out perfectly.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Arrays;

public class ValidAnagram {

    // Brute Force - O(n log n) by sorting
    public boolean isAnagramBrute(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a, b);
    }

    // Optimized - O(n) with character count array
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int i : count) {
            if (i != 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        ValidAnagram solver = new ValidAnagram();
        String s = "anagram", t = "nagaram";

        System.out.println("--- Valid Anagram Demonstration ---");
        System.out.printf("String 1: %s, String 2: %s\n", s, t);

        boolean result = solver.isAnagram(s, t);
        System.out.println("Step 1: Compare lengths. Both are length " + s.length());
        System.out.println("Step 2: Maintain frequency count arrays.");
        System.out.println("Is Anagram: " + result);
    }
}

Conclusion

Solving the Valid Anagram problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.