Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-003 · FOCUSED PRACTICE

Valid Anagram

Foundation · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 14645 deterministic checks. Learner drafts are not executed.

Understand the problem

Return whether two strings are anagrams: they must contain exactly the same lowercase letters with the same multiplicities, regardless of order.

  • s and t are non-null strings of 0–100,000 characters, each in lowercase a–z. Other alphabets, uppercase, and null are outside the contract.
  • Empty strings are anagrams of one another. Different lengths cannot be anagrams. Spaces are not silently ignored; they are excluded by the input alphabet.
  • Return boolean. Strings are preserved. Character counts fit int because each length is at most 100,000.

Examples

  1. Input: s="anagram", t="nagaram"
    Output: true

    Every letter has equal multiplicity in both strings.

  2. Input: s="aab", t="abb"
    Output: false

    The sets of letters match, but the counts of a and b do not.

  3. Input: s="", t=""
    Output: true

    All 26 count differences are zero.

Before you start

  • Character multiplicity rather than membership
  • Explicit lowercase alphabet and count-array indexing

Recognize the structure

Anagrams are an equivalence relation on symbol-count vectors. Set membership loses repeated occurrences. A fixed 26-letter contract permits direct array indexing without hash-table assumptions; unrestricted Unicode would require a different representation and normalization policy.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

No unsaved text changes · 92/20,000 characters

Self-review

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

What information remains unchanged when letters are rearranged?

Hint 2

Represent each letter by its count.

Hint 3

Subtract one string’s counts from the other and test the final vector.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Sort both character copies

Convert each string to a char array, sort, and compare. For "baba" and "aabb", both canonical arrays become "aabb". Equality of sorted arrays is equivalent to matching multiplicities. The copies cost O(n+m) memory; sorting takes O(n log n+m log m) time for lengths n and m.

Improve the baseline

Discard unnecessary ordering

The question cares how many of each letter exists, not its sorted order. Allocate 26 signed count differences.

Accumulate both sides

For equal-length strings, increment the slot from s and decrement the slot from t at each index. An intermediate difference need not be zero.

Inspect every final slot

A positive slot means surplus in s; a negative slot means surplus in t. Accept only if all differences are zero after every character is processed.

Why it is correct

Initialization

All differences start at zero and describe empty prefixes of both strings.

Preservation

After i positions, each slot equals occurrences in s[0,i) minus occurrences in t[0,i). The paired increment/decrement preserves that exact meaning even when different characters are processed.

Final equivalence

Equal lengths alone are insufficient, but all final count differences zero means each letter occurs equally often. Conversely anagrams give zero in every slot. The finite scan and 26-slot check terminate.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Arrays;
public final class Solution {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] difference = new int[26];
        for (int i = 0; i < s.length(); i++) {
            difference[s.charAt(i) - 'a']++;
            difference[t.charAt(i) - 'a']--;
        }
        for (int count : difference) if (count != 0) return false;
        return true;
    }
    public static boolean baseline(String s, String t) {
        char[] a = s.toCharArray(), b = t.toCharArray();
        Arrays.sort(a); Arrays.sort(b);
        return Arrays.equals(a, b);
    }
}

Read the meaningful blocks

Reject unequal lengths first

The paired scan reads corresponding indices safely only after this check.

Index under the declared alphabet

char-a lies in 0..25 only for lowercase a–z; the method is not a Unicode validator.

Check after the whole scan

A nonzero intermediate difference may be canceled later; early rejection there would be incorrect.

Complexity

O(n+m+26) time, including the fixed-alphabet check; unequal lengths can be rejected immediately. O(26)=O(1) auxiliary space under this fixed alphabet.

The sorted-copy baseline uses O(n log n+m log m) time and O(n+m) character-copy storage. Do not compare this deterministic count-array bound to an unstated unbounded alphabet model.

Exact-state walkthroughs

Reveal normal and boundary traces

Imbalances cancel

Input: {"s":"ab","t":"ba"} · Result: true

Step 1 of 5: Compare lengths before scanning paired positions.

Unequal lengths cannot have equal multiplicities.

State after this step
VariableValue
sLength2
tLength2
See the affected Java block
 1 import java.util.Arrays;
 2 public final class Solution {
 3     public static boolean isAnagram(String s, String t) {
 4         if (s.length() != t.length()) return false;
 5         int[] difference = new int[26];
 6         for (int i = 0; i < s.length(); i++) {
 7             difference[s.charAt(i) - 'a']++;
 8             difference[t.charAt(i) - 'a']--;
 9         }
10         for (int count : difference) if (count != 0) return false;
11         return true;
12     }
13     public static boolean baseline(String s, String t) {
14         char[] a = s.toCharArray(), b = t.toCharArray();
15         Arrays.sort(a); Arrays.sort(b);
16         return Arrays.equals(a, b);
17     }
18 }
19

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Compare lengths before scanning paired positions.

    Unequal lengths cannot have equal multiplicities.

    sLength
    2
    tLength
    2
  2. Add the s occurrence and subtract the t occurrence.

    Each slot is the count in the processed s prefix minus the processed t prefix.

    i
    0
    sSymbol
    "a"
    tSymbol
    "b"
    difference
    [1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  3. Add the s occurrence and subtract the t occurrence.

    Each slot is the count in the processed s prefix minus the processed t prefix.

    i
    1
    sSymbol
    "b"
    tSymbol
    "a"
    difference
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  4. Inspect the complete difference vector.

    Only the final count differences establish anagram equivalence.

    difference
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  5. Return the contract result.

    The completed state satisfies the declared output and mutation contract.

    result
    true

Same alphabet, different counts

Input: {"s":"aab","t":"abb"} · Result: false

Step 1 of 6: Compare lengths before scanning paired positions.

Unequal lengths cannot have equal multiplicities.

State after this step
VariableValue
sLength3
tLength3
See the affected Java block
 1 import java.util.Arrays;
 2 public final class Solution {
 3     public static boolean isAnagram(String s, String t) {
 4         if (s.length() != t.length()) return false;
 5         int[] difference = new int[26];
 6         for (int i = 0; i < s.length(); i++) {
 7             difference[s.charAt(i) - 'a']++;
 8             difference[t.charAt(i) - 'a']--;
 9         }
10         for (int count : difference) if (count != 0) return false;
11         return true;
12     }
13     public static boolean baseline(String s, String t) {
14         char[] a = s.toCharArray(), b = t.toCharArray();
15         Arrays.sort(a); Arrays.sort(b);
16         return Arrays.equals(a, b);
17     }
18 }
19

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Compare lengths before scanning paired positions.

    Unequal lengths cannot have equal multiplicities.

    sLength
    3
    tLength
    3
  2. Add the s occurrence and subtract the t occurrence.

    Each slot is the count in the processed s prefix minus the processed t prefix.

    i
    0
    sSymbol
    "a"
    tSymbol
    "a"
    difference
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  3. Add the s occurrence and subtract the t occurrence.

    Each slot is the count in the processed s prefix minus the processed t prefix.

    i
    1
    sSymbol
    "a"
    tSymbol
    "b"
    difference
    [1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  4. Add the s occurrence and subtract the t occurrence.

    Each slot is the count in the processed s prefix minus the processed t prefix.

    i
    2
    sSymbol
    "b"
    tSymbol
    "b"
    difference
    [1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  5. Inspect the complete difference vector.

    Only the final count differences establish anagram equivalence.

    difference
    [1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  6. Return the contract result.

    The completed state satisfies the declared output and mutation contract.

    result
    false

Test the contract

  1. Input: s="a", t=""
    Output: false

    Length mismatch.

  2. Input: s="aa", t="aa"
    Output: true

    Repeated multiplicity.

  3. Input: s="ab", t="ba"
    Output: true

    Order does not matter.

  4. Input: s="abc", t="abd"
    Output: false

    One differing symbol.

Common mistakes and counterexamples

Compare letter sets only

Counterexample: "aab" and "abb" are not anagrams.

Keep multiplicities.

Reject on an intermediate nonzero count

Counterexample: "ab" and "ba" have a temporary imbalance but are anagrams.

Inspect final differences after all characters.

Use a fixed array without an alphabet contract

Counterexample: Uppercase A does not map into char-a slots.

Keep the input contract or change the representation.

Follow-ups

Accept arbitrary Unicode code points.

Count int code points and specify case folding/normalization explicitly. Java char units do not automatically correspond to complete characters.

Group a list of anagrams.

Use the entire count vector as a stable key. A sum of character codes is insufficient because different multisets can share that sum.

Find every anagram window inside a longer string.

Maintain a fixed-length sliding count difference, updating only entering and leaving symbols. Define empty-pattern behavior and compare windows rather than the entire strings.

Related foundations

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These are standard algorithmic tasks; no company-frequency or interview-outcome claims are made.