Valid Anagram in Java DSA: Sorting, HashMaps, and the Count Array Trick

Solve Valid Anagram in Java DSA three ways — sorting, a HashMap counter, and the O(1) count array. Full step-by-step dry runs for beginners.

1. Introduction

Valid Anagram in Java is one of those warm-up problems that hides a neat lesson about counting. Two words are anagrams when they use the exact same letters, just shuffled around. So “listen” and “silent” are anagrams, but “hello” and “world” are not.

The task is short. You get two strings. You return true if one is a rearrangement of the other, and false otherwise.

There is a small catch that trips people up. Length matters first. If the two strings have different lengths, they can never be anagrams, so you can bail out early.

We build the answer in three steps, like always. Sorting both strings is the easy first idea. A hash map that counts letters is the next step up. The count array of size 26 is the lean version interviewers love to see.

Every approach gets a full, step-by-step dry run on the same words. Nothing is skipped, so you can watch each letter change the counts and see exactly why the answer comes out true or false.

2. Understanding the Problem

Let us pin down the rules before we write any code.

• You get two strings, for example s = “anagram” and t = “nagaram”.
• Return true when t is a rearrangement of s.
• Both strings must have the same length, or the answer is instantly false.
• Every letter must appear the same number of times in both strings.

For our pair the answer is true, because both words are made of three a’s, one g, one m, one n, and one r. We will also trace a false pair, s = “anagram” and t = “nagaraz”, where a stray z spoils the match.

3. Concepts You Need Here

3.1 Anagrams Are Just Equal Letter Counts

Two strings are anagrams when each letter shows up the same number of times in both. Order does not matter at all. So the whole problem boils down to comparing letter counts.

• Same length is a must, so check that first.
• Then confirm every letter count matches between the two strings.

3.2 Counting With a Map or an Array

There are two clean ways to count letters. A hash map stores each character with its count, which works for any alphabet. A plain array of 26 slots works when the input is only lowercase a to z, and it is faster because array access is cheap.

• A map is flexible and handles unicode or mixed characters.
• An array of 26 is leaner when the letters are limited to a to z.

4. Approach 1: Sort Both Strings

Sort the letters of both strings, then compare them character by character. If two words are anagrams, their sorted forms are identical. It is the simplest idea to reach for, even if it is not the fastest.

4.1 Pseudocode

if length(s) != length(t):
    return false
 
a = sort(s)   // sorted characters of s
b = sort(t)   // sorted characters of t
 
return a equals b

4.2 Pseudocode Explained

The idea is simple. If two words are anagrams, sorting them gives the same result. So we sort both and check if they match.

• First we check the lengths. If they are different, the words cannot be anagrams, so we stop early and save time.
• Then we sort. Sorting drops the original order and lines up the letters the same way for both words.
• Last we compare. Same letters in the same order means the two words are anagrams.

4.3 Java Code

import java.util.*;
 
public class ValidAnagramSort {
 
    public static boolean isAnagram(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);
    }
 
    public static void main(String[] args) {
        System.out.println(isAnagram("anagram", "nagaram")); // true
        System.out.println(isAnagram("anagram", "nagaraz")); // false
    }
}

4.4 Java Code Explained

This is the same plan, written in Java. Java cannot sort a String directly, so we first turn each String into a char array, which Arrays.sort can handle.

• Lines 6 to 8 check the lengths. If they differ, we return false and never run the sorting code.
• Lines 9 and 10 turn each string into a char array, since a String cannot be sorted on its own.
• Then lines 11 and 12 sort both arrays. After this, two anagrams look exactly the same.
• Line 13 uses Arrays.equals to compare them. It checks the arrays and stops at the first spot that does not match.

4.5 Dry Run of the Sort Approach

Let us trace the true pair first, s = “anagram” and t = “nagaram”. Both have length 7, so the length check passes and we move on to sorting.

Here is what each string looks like before and after Arrays.sort. Sorting arranges the letters alphabetically, so equal anagrams collapse to the exact same sequence.

Now compare the two sorted arrays slot by slot. Every position matches, so Arrays.equals returns true.

Now the false pair, s = “anagram” and t = “nagaraz”. Lengths are still 7, so we sort both again.

This time the compare stops early at the first mismatch. Index 4 holds m in s but n in t, so Arrays.equals returns false right there.

4.6 Reading the Dry Run

Let us walk both traces and see exactly what sorting buys us.

The true pair: anagram vs nagaram.

Both strings pass the length check because each has 7 characters. That check is cheap and it saves us from sorting when the answer is obviously false.

• The word anagram holds the letters a, n, a, g, r, a, m in that order.
• Sorting reshuffles them into a, a, a, g, m, n, r, grouping the three a’s up front.
• The word nagaram sorts to the exact same sequence, a, a, a, g, m, n, r.

Because both sorted arrays are identical, the compare passes at every index and the method returns true. Sorting worked by forcing both words into one canonical order, so any two anagrams line up perfectly.

The false pair: anagram vs nagaraz.

Here the lengths still match, so we sort both words again. The word nagaraz has a z where the true partner had an m.

• The string s sorts to a, a, a, g, m, n, r as before.
• Meanwhile t sorts to a, a, a, g, n, r, z, since z is the largest letter and lands at the end.
• So the first three slots match, and slot 3 matches on g.

At index 4 the two arrays disagree: s has m while t has n. Arrays.equals notices the mismatch and returns false immediately, without checking the rest. That early stop is why the compare is quick even when the words are long.

4.7 Time and Space Cost

• Time is O(n log n), because sorting dominates the work.
• Space is O(n) for the two character arrays we build and sort.

Sorting is clean and short, but that log n factor is wasted effort. We are about to count letters instead, which drops the time to linear.

5. Approach 2: Count Letters With a HashMap

Skip the sorting. Walk s and add one to each letter’s count. Then walk t and subtract one for each letter. If every count lands back at zero, the words are anagrams. A negative count mid-way means t has a letter that s cannot cover, so we can stop early.

5.1 Pseudocode

if length(s) != length(t):
    return false
 
count = empty map from char to int
 
for ch in s:
    count[ch] = count[ch] + 1   // add one for s
 
for ch in t:
    count[ch] = count[ch] - 1   // remove one for t
    if count[ch] < 0:
        return false
 
return true

5.2 Pseudocode Explained

Think of the map as a score for each letter. The first word adds to the score, the second word takes away from it. If every score ends at zero, the words match.

• The first loop reads s and adds one for each letter. Now the map knows how many of each letter s has.
• The second loop reads t and takes one away for each letter.
• If any count drops below zero, t has a letter that s does not have enough of. So we return false right away.
• If nothing goes below zero and the lengths were equal, every count must end at zero. That means the words are anagrams.

5.3 Java Code

import java.util.*;
 
public class ValidAnagramMap {
 
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> count = new HashMap<>();
        for (char ch : s.toCharArray()) {
            count.put(ch, count.getOrDefault(ch, 0) + 1);
        }
        for (char ch : t.toCharArray()) {
            count.put(ch, count.getOrDefault(ch, 0) - 1);
            if (count.get(ch) < 0) {
                return false;
            }
        }
        return true;
    }
 
    public static void main(String[] args) {
        System.out.println(isAnagram("anagram", "nagaram")); // true
        System.out.println(isAnagram("anagram", "nagaraz")); // false
    }
}

5.4 Java Code Explained

The Java code follows the same score idea. The one helper to know is getOrDefault, which gives back 0 for a letter we have not seen yet, so we never hit a null.

• Lines 6 to 8 check the lengths, same as before.
• Line 9 makes the map. The keys are letters and the values are their counts.
• Lines 10 to 12 read s and add one for each letter. getOrDefault(ch, 0) returns 0 for a new letter, so adding one always works.
• Lines 13 to 18 read t and take one away for each letter. Right after, we check the count, and a value below zero ends the method.
• Line 19 runs only when no count ever went below zero, so returning true here is safe.

5.5 Dry Run of the HashMap Approach

True pair first, s = “anagram” and t = “nagaram”. Lengths match at 7, so we start counting. The first table shows the count-up pass over s.

Now the count-down pass over t. Each letter drops by one. Watch that no count ever goes below zero.

Every count finished at zero and none dipped negative, so the method returns true. Now the false pair, s = “anagram” and t = “nagaraz”. The count-up pass over s is exactly the same as before, ending at {a:3, n:1, g:1, r:1, m:1}. The count-down over t is where it breaks.

5.6 Reading the Dry Run

Let us go pass by pass and watch the map fill up and drain.

Count-up pass over s (anagram).

This pass just tallies the letters of s. The map starts empty and grows one entry at a time.

• At i=0 the letter a is new, so its count becomes 1.
• Reading i=1 adds n with count 1, and i=2 bumps a up to 2.
• Moving through i=3 and i=4 adds g and r, each at count 1.
• By i=5 the third a arrives, so a reaches 3, and i=6 adds m at 1.

After the whole pass the map reads {a:3, n:1, g:1, r:1, m:1}. That is the exact letter fingerprint of the word anagram.

Count-down pass over t (nagaram), the true case.

Now every letter of t pulls its own count down by one. If s and t are true anagrams, each drop lands on a count that was waiting for it.

• At j=0 the n drops from 1 to 0, and j=1 pulls the first a from 3 to 2.
• Reading j=2 sends g to 0, then j=3 drops a again to 1.
• Stepping to j=4 sends r to 0, and j=5 empties a down to 0.
• Finally j=6 drops m to 0, so every single count is now zero.

No count ever went negative, which tells us t never asked for a letter that s had run out of. Since the lengths matched too, the method safely returns true.

Count-down pass over t (nagaraz), the false case.

The first six steps are identical to the true case, because nagaraz shares its first six letters’ multiset with nagaram. The break comes at the very end.

• Through j=0 to j=5 the counts fall exactly as before, none going negative.
• At j=6 the letter is z, which was never in s, so its count starts at 0 and drops to -1.
• That negative count means t has a letter s cannot cover, so we return false at once.

Notice the early exit. We did not even need to finish checking or scan the map at the end. One negative count was enough proof that the words differ.

5.7 Time and Space Cost

• Time is O(n), since we walk each string once with cheap map operations.
• Space is O(k), where k is the number of distinct letters stored in the map.

This beats sorting on speed. Still, a HashMap carries boxing and hashing overhead. When the input is only lowercase a to z, we can swap the map for a tiny array and go even faster.

6. Approach 3: Count Array of 26

For lowercase English letters, a plain int array of 26 slots replaces the map. Slot 0 is a, slot 1 is b, and so on. Add one for each letter in s, subtract one for each letter in t, then check that every slot is zero. No hashing, no boxing, just fast array math. This is the answer interviewers hope to see.

6.1 Pseudocode

if length(s) != length(t):
    return false
 
count = array of 26 zeros
 
for ch in s:
    count[ch - 'a'] = count[ch - 'a'] + 1
 
for ch in t:
    count[ch - 'a'] = count[ch - 'a'] - 1
 
for value in count:
    if value != 0:
        return false
 
return true

6.2 Pseudocode Explained

This is the same map idea, but simpler. There are only 26 lowercase letters, so we do not need a map. A plain array with one slot per letter works, and it is faster.

• The ch minus ‘a’ part gives each letter a slot. It turns ‘a’ into 0, ‘b’ into 1, and so on up to ‘z’ at 25.
• One loop adds one for each letter in s. The next loop takes one away for each letter in t.
• At the end we check all 26 slots. If any slot is not zero, some letter did not match, so the words are different.

6.3 Java Code

public class ValidAnagramCount {
 
    public static 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 value : count) {
            if (value != 0) {
                return false;
            }
        }
        return true;
    }
 
    public static void main(String[] args) {
        System.out.println(isAnagram("anagram", "nagaram")); // true
        System.out.println(isAnagram("anagram", "nagaraz")); // false
    }
}

6.4 Java Code Explained

The code is short because the array does most of the work. The nice part is that one loop reads both strings, so we go through the input only once.

• Lines 4 to 6 check the lengths, as usual.
• Line 7 makes the array of 26 counts. Java fills a new int array with zeros, so each slot starts at 0.
• Lines 8 to 11 use one loop for both strings. Since s and t are the same length, index i reaches both, so we add for s and take away for t in one step.
• Lines 12 to 16 check the finished array. The first slot that is not zero means a letter did not match, so we return false.
• Line 17 returns true only when every slot is zero, which means the letters match.

6.5 Dry Run of the Count Array

True pair first, s = “anagram” and t = “nagaram”. To keep the table readable we show only the slots that are not zero after each step. The single loop touches both strings, so each row bumps the s letter up and the t letter down in the same step.

The final sweep finds every slot at zero, so the method returns true. Now the false pair, s = “anagram” and t = “nagaraz”. Only the last step changes, because t’s last letter is z instead of m.

This time the final sweep hits slot m at 1 and slot z at -1. Both are nonzero, so the method returns false.

6.6 Reading the Dry Run

Let us step through the single loop and watch the 26 slots wobble around zero.

The true pair, step by step.

Each step touches two slots: the s letter goes up, the t letter goes down. Because s and t are true anagrams, these bumps keep cancelling out as we go.

• At i=0 we add a (slot a becomes 1) and subtract n (slot n becomes -1).
• Reading i=1 adds n back to 0 and subtracts a back to 0, so both settle.
• Stepping to i=2 adds a (1) and subtracts g (-1), leaving two slots off balance.
• Then i=3 adds g and subtracts a, and both return to zero again.
• By i=4, i=5, and i=6 the letters r, a, and m are the same in both strings, so each cancels itself instantly.

The counts bounce above and below zero during the loop, which is fine. What matters is the end state. After the last step every slot sits at zero, so the final sweep confirms a true anagram.

The false pair, step by step.

The first six steps run exactly like the true case, since nagaraz matches nagaram up to that point. The difference lands on the final letter.

• Through i=0 to i=5 the slots rise and fall and keep balancing out to zero.
• At i=6 we add m, so slot m climbs to 1, and we subtract z, so slot z drops to -1.
• Those two slots never get a chance to cancel, because the loop is over.

Now the final sweep walks all 26 slots. It finds m at 1 and z at -1, both nonzero, so it returns false. The leftover counts are the fingerprint of the mismatch: s had an extra m, and t had an extra z.

6.7 Comparing the Three Traces

7. Comparing the Three Approaches

All three return the same answer. They just pay different prices to get there.

The two counting versions share the same linear time. What sets them apart is memory and overhead. The array of 26 uses a fixed, tiny amount of space and skips all hashing, so it edges out the map on raw speed.

In an interview, mention sorting first to show you know it, then pivot to counting. Land on the count array for lowercase input, and name the map as your fallback for wider alphabets. That progression tells a clean story.

8. Common Mistakes and Edge Cases

A few small traps catch beginners on Valid Anagram. Keep them in mind.

• Forgetting the length check makes the counting logic do extra work and can hide bugs.
• Comparing strings with equals instead of comparing sorted arrays gives wrong results.
• Using the 26-slot array on uppercase or unicode input breaks the ch minus ‘a’ math.
• Two empty strings are anagrams of each other, so the answer should be true.
• Strings of different lengths, like “abc” and “abcd”, are never anagrams.

Run the empty-string case and a different-length case through your code before you call it done. They catch more bugs than any ordinary input will.

9. Conclusion

Valid Anagram in Java looks tiny, yet it teaches a habit you will reuse everywhere: turn a comparison into a count. Once you see two strings as bags of letters, the whole problem clicks.

Our seven-letter traces showed the payoff clearly. Sorting forced both words into one order and compared them. The map counted up then down, and the array of 26 did the same thing with almost no memory.

So take the pattern, not just the answer. When order does not matter, count instead of sort. Reach for a fixed array when the alphabet is small, and keep the map handy for anything bigger.

That counting habit turns many string and array problems from tricky into routine. It will serve you well on the harder problems waiting further down the list.

10. Further Reading

• LeetCode Valid Anagram problem — practice the original problem and submit your own solution.
• Oracle Java HashMap documentation — the official reference for the map used in approach two.
• Previous in this series: Two Sum in Java — find two numbers that add to a target using a single-pass hash map.
• Next in this series: Group Anagrams in Java — bucket words together by their sorted or counted letter signature.