Valid Anagram in Java

When I first saw this problem, my goal was simple: check whether two strings are anagrams of each other.

Understanding the Problem

We are given two strings s and t. We need to return true if t is an anagram of s, otherwise false.

Before jumping into code, I tried to clearly understand what an anagram means.

Two strings are anagrams if:

• They have the same length
• They contain the same characters
• Each character appears the same number of times

Example:

s = "anagram"
t = "nagaram"

These are anagrams.

s = "rat"
t = "car"

These are not anagrams.

Initial Thought

My first instinct was to compare both strings directly. But that doesn’t work because the order of characters can be different.

Then I thought about sorting both strings and comparing them. That works, but sorting takes extra time.

So I looked for a more optimal way.

Key Idea

Instead of worrying about order, I focused on character frequency.

If both strings have exactly the same count for every character, then they must be anagrams.

Since the problem states that inputs contain only lowercase English letters, I can use a fixed-size array of length 26.

Approach

1. First, check if the lengths of both strings are equal. If not, return false immediately.
2. Create an integer array of size 26 to store character frequencies.
3. Traverse the first string and increment the count for each character.
4. Traverse the second string and decrement the count for each character.
5. Finally, check if all values in the array are zero.

If all values are zero, both strings have identical character counts.

Code

class Solution {
    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']++;
        }

        for (int i = 0; i < t.length(); i++) {
            count[t.charAt(i) - 'a']--;
        }

        for (int c : count) {
            if (c != 0) {
                return false;
            }
        }

        return true;
    }
}

Why This Works

The array acts like a frequency tracker.

• Every character in s increases the count
• Every character in t decreases the count

If both strings have the same characters in the same frequency, all values will cancel out and become zero.

If any value is not zero, it means there is a mismatch.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

The space is constant because the array size is always 26.

Alternative Thoughts

I also considered using a HashMap. That works well when the input is not limited to lowercase letters (for example, Unicode characters).

Another approach is sorting both strings and comparing them, but that is less efficient.

Conclusion

The main insight for this problem is shifting focus from order to frequency.

Once I thought in terms of counting characters, the solution became straightforward and efficient.

This problem is a good example of how choosing the right data structure simplifies the logic.