Backend interview prep

Start Learning

String Anagram

Java coding interview problem for String Coding: String Anagram.

Checking whether two strings are Anagrams is one of the most frequently asked String interview questions in Java.

Although the problem appears simple, it evaluates several important programming concepts, including:

  • String manipulation
  • Character Frequency
  • Arrays
  • Sorting
  • HashMap
  • Time Complexity
  • Space Optimization

Interviewers often ask several follow-up questions such as:

  • Can you solve it without sorting?
  • Can you ignore uppercase and lowercase letters?
  • Can you ignore spaces and punctuation?
  • Which solution is the most efficient?
  • Can you solve it in linear time?

Understanding multiple approaches prepares you for all these interview variations.

Problem Statement

Given two strings, determine whether they are anagrams of each other.

Two strings are called anagrams if:

  • They contain exactly the same characters.
  • Every character appears the same number of times.
  • Character order does not matter.

Return:

  • true if both strings are anagrams.
  • false otherwise.

Example 1

Input

listen

silent

Output

true

Example 2

Input

race

care

Output

true

Example 3

Input

java

spring

Output

false

Example 4

Input

triangle

integral

Output

true

What is an Anagram?

An anagram is a word or phrase formed by rearranging the letters of another word or phrase.

Example

listen

Rearranged

silent

Both contain

l

i

s

t

e

n

Therefore

Anagram

Another Example

evil

vile

Characters

e

v

i

l

Same frequency.

Result

Anagram

Non-Anagram Example

java

spring

Different characters.

Result

Not Anagram

Why is String Anagram Asked in Interviews?

This problem helps interviewers evaluate your understanding of:

  • Character counting
  • Arrays
  • Sorting
  • HashMap
  • Frequency counting
  • String traversal
  • Time Complexity
  • Space Complexity

It also forms the basis for many advanced interview problems.

Examples include:

  • Group Anagrams
  • Valid Anagram
  • Character Frequency
  • First Non-Repeating Character
  • Find Duplicate Characters

Real-World Applications

Checking anagrams has several practical applications.

Spell Checkers

Spell-check systems compare character frequencies.

Search Engines

Search engines normalize words before indexing.

Plagiarism Detection

Some text comparison algorithms analyze character distribution.

Cryptography

Certain encryption techniques compare rearranged text.

Competitive Programming

Many string-based coding problems rely on anagram detection.

Understanding Character Frequency

The key idea behind an anagram is:

The frequency of every character must be identical.

Example

listen

Frequency

l → 1

i → 1

s → 1

t → 1

e → 1

n → 1

Second String

silent

Frequency

s → 1

i → 1

l → 1

e → 1

n → 1

t → 1

Every frequency matches.

Result

true

Sorting vs Frequency Counting

There are two common approaches.

Sorting

Sort both strings.

Example

listen

↓

eilnst

silent

↓

eilnst

Equal?

Yes

Frequency Counting

Instead of sorting,

count every character.

Example

listen

a → 0

b → 0

...

e → 1

i → 1

...

Repeat for the second string.

Compare frequencies.

This approach is usually faster.

Mathematical Concept

Suppose

CARE

Sorted

ACER

Second String

RACE

Sorted

ACER

Both sorted strings are identical.

Therefore

Anagram

Visual Representation

Input

listen

l i s t e n

Sort

e i l n s t

Input

silent

s i l e n t

Sort

e i l n s t

Comparison

Equal

↓

true

Dry Run

Input

listen

silent

Step 1

Convert to character arrays.

[l i s t e n]

[s i l e n t]

Step 2

Sort both arrays.

[e i l n s t]

[e i l n s t]

Step 3

Compare.

Equal

Return

true

Another Example

java

spring

Sorted

aajv

eginprs

Lengths differ.

Return

false

Approach 1 — Using Sorting (Recommended for Beginners)

The easiest way to check whether two strings are anagrams is:

  1. Convert them into character arrays.
  2. Sort both arrays.
  3. Compare the sorted arrays.

If they are identical,

the strings are anagrams.

Algorithm

  1. Check whether both strings have the same length.
  2. Convert them into character arrays.
  3. Sort both arrays.
  4. Compare the arrays.
  5. Return the comparison result.

Java Program

import java.util.Arrays;

public class StringAnagram {

    public static boolean isAnagram(String first, String second) {

        if (first.length() != second.length()) {
            return false;
        }

        char[] firstArray = first.toCharArray();
        char[] secondArray = second.toCharArray();

        Arrays.sort(firstArray);
        Arrays.sort(secondArray);

        return Arrays.equals(firstArray, secondArray);

    }

    public static void main(String[] args) {

        System.out.println(isAnagram("listen", "silent"));

        System.out.println(isAnagram("java", "spring"));

    }

}

Output

true

false

Step-by-Step Code Explanation

Check the lengths.

if (first.length() != second.length())

Different lengths can never form anagrams.

Convert to character arrays.

first.toCharArray();

second.toCharArray();

Sort both arrays.

Arrays.sort(firstArray);

Arrays.sort(secondArray);

Compare.

Arrays.equals(firstArray, secondArray);

Return

true

only if both arrays are identical.

Dry Run of Sorting Approach

Input

race

care
Step First Second
Original race care
Character Array [r,a,c,e] [c,a,r,e]
Sorted [a,c,e,r] [a,c,e,r]
Comparison Equal true

Advantages

  • Easy to understand.
  • Simple implementation.
  • Excellent for beginners.
  • Frequently accepted in coding interviews.

Drawbacks

  • Sorting increases time complexity.
  • Not the most optimal solution.

Approach 2 — Using Character Frequency Array (Optimal)

Instead of sorting,

count the frequency of every character.

If all frequencies become zero,

the strings are anagrams.

This is the preferred interview solution because it runs in linear time.

Algorithm

  1. Check string lengths.
  2. Create a frequency array.
  3. Traverse the first string and increment the frequency.
  4. Traverse the second string and decrement the frequency.
  5. Verify that every frequency is zero.
  6. Return the result.

Java Program

public class StringAnagramFrequency {

    public static boolean isAnagram(String first, String second) {

        if (first.length() != second.length()) {
            return false;
        }

        int[] frequency = new int[256];

        for (char ch : first.toCharArray()) {
            frequency[ch]++;
        }

        for (char ch : second.toCharArray()) {
            frequency[ch]--;
        }

        for (int value : frequency) {

            if (value != 0) {
                return false;
            }

        }

        return true;

    }

    public static void main(String[] args) {

        System.out.println(isAnagram("triangle", "integral"));

        System.out.println(isAnagram("java", "python"));

    }

}

Output

true

false

Step-by-Step Code Explanation

Create a frequency array.

int[] frequency = new int[256];

Increase frequency.

frequency[ch]++;

Decrease frequency.

frequency[ch]--;

Verify frequencies.

if (value != 0)

Return

false

because the characters differ.

If every frequency becomes zero,

return

true

Time & Space Complexity

Approach Time Extra Space
Sorting O(n log n) O(n)
Frequency Array O(n) O(1)*

Note: The frequency-array solution uses a fixed-size array (256 entries for extended ASCII), so the extra space is considered O(1) relative to the input size.

Where:

  • n = length of the strings.

Comparison of Approaches

Feature Sorting Frequency Array
Interview Friendly ⭐⭐⭐⭐ ⭐⭐⭐⭐⭐
Easy to Understand ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐
Performance ⭐⭐⭐ ⭐⭐⭐⭐⭐
Time Complexity O(n log n) O(n)
Extra Space O(n) O(1)*

Advantages

  • Both approaches are simple and reliable.
  • Sorting is easy to explain and implement.
  • Frequency counting provides optimal linear-time performance.
  • Both are commonly asked in Java coding interviews.
  • They form the foundation for advanced problems such as Group Anagrams and Valid Anagram.

Drawbacks

  • Sorting is slower because of the sorting operation.
  • The frequency-array solution assumes a bounded character set (such as ASCII) unless adapted for Unicode.
  • Neither approach ignores spaces, punctuation, or character case without preprocessing.

In Part 2, we'll cover:

  • Approach 3 – Using HashMap
  • Approach 4 – Using Java Streams (Java 8+)
  • Approach 5 – Using Arrays.equals() with Frequency Arrays
  • Valid Anagram Ignoring Spaces and Case
  • Unicode Considerations
  • Comparison of All Approaches
  • Common Interview Mistakes
  • Edge Cases
  • Interview Follow-up Questions
  • Related Problems
  • Key Takeaways
  • Frequently Asked Interview Questions
  • Interview Tips

Approach 3 — Using HashMap

A HashMap stores the frequency of every character.

The idea is simple:

  1. Count every character in the first string.
  2. Reduce the count using the second string.
  3. If every frequency becomes zero, the strings are anagrams.

This approach is especially useful for Unicode strings, where a fixed-size frequency array may not be sufficient.

Algorithm

  1. Check whether both strings have the same length.
  2. Create a HashMap<Character, Integer>.
  3. Count characters from the first string.
  4. Decrease the count using the second string.
  5. Verify every frequency becomes zero.

Java Program

import java.util.HashMap;
import java.util.Map;

public class StringAnagramHashMap {

    public static boolean isAnagram(String first, String second) {

        if (first.length() != second.length()) {
            return false;
        }

        Map<Character, Integer> map = new HashMap<>();

        for (char ch : first.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        for (char ch : second.toCharArray()) {

            if (!map.containsKey(ch)) {
                return false;
            }

            map.put(ch, map.get(ch) - 1);

            if (map.get(ch) == 0) {
                map.remove(ch);
            }

        }

        return map.isEmpty();

    }

    public static void main(String[] args) {

        System.out.println(isAnagram("listen", "silent"));

        System.out.println(isAnagram("hello", "world"));

    }

}

Output

true

false

Advantages

  • Works well for Unicode.
  • Easy to extend.
  • Excellent for frequency-based problems.

Drawbacks

  • More memory than frequency arrays.
  • More verbose implementation.

Approach 4 — Using Java Streams (Java 8+)

Java Streams provide a modern functional approach.

We first sort both strings using streams and then compare them.

Java Program

import java.util.stream.Collectors;

public class StringAnagramStreams {

    private static String sort(String word) {

        return word.chars()
                .sorted()
                .mapToObj(c -> String.valueOf((char) c))
                .collect(Collectors.joining());

    }

    public static boolean isAnagram(String first, String second) {

        if (first.length() != second.length()) {
            return false;
        }

        return sort(first).equals(sort(second));

    }

    public static void main(String[] args) {

        System.out.println(isAnagram("race", "care"));

    }

}

Output

true

Advantages

  • Modern Java.
  • Functional programming style.
  • Readable once familiar with Streams.

Drawbacks

  • More overhead than loops.
  • Usually not preferred in coding interviews.

Approach 5 — Using Arrays.equals() with Frequency Arrays

Instead of sorting,

build two frequency arrays and compare them using Arrays.equals().

Algorithm

  1. Create two frequency arrays.
  2. Count characters separately.
  3. Compare both arrays.

Java Program

import java.util.Arrays;

public class StringAnagramFrequencyArrays {

    public static boolean isAnagram(String first, String second) {

        if (first.length() != second.length()) {
            return false;
        }

        int[] frequency1 = new int[256];
        int[] frequency2 = new int[256];

        for (char ch : first.toCharArray()) {
            frequency1[ch]++;
        }

        for (char ch : second.toCharArray()) {
            frequency2[ch]++;
        }

        return Arrays.equals(frequency1, frequency2);

    }

    public static void main(String[] args) {

        System.out.println(isAnagram("triangle", "integral"));

    }

}

Output

true

Advantages

  • Easy to understand.
  • No sorting required.
  • Linear time.

Drawbacks

  • Uses two frequency arrays instead of one.
  • Optimizable by using a single array.

Valid Anagram Ignoring Spaces and Case

Many interviewers modify the problem as follows:

Ignore spaces, punctuation, and uppercase/lowercase letters.

Example

Input

Dormitory

Dirty Room

Processed Strings

dormitory

dirtyroom

Output

true

Java Program

import java.util.Arrays;

public class ValidAnagram {

    public static boolean isAnagram(String first, String second) {

        first = first.replaceAll("[^a-zA-Z0-9]", "")
                     .toLowerCase();

        second = second.replaceAll("[^a-zA-Z0-9]", "")
                       .toLowerCase();

        if (first.length() != second.length()) {
            return false;
        }

        char[] firstArray = first.toCharArray();
        char[] secondArray = second.toCharArray();

        Arrays.sort(firstArray);
        Arrays.sort(secondArray);

        return Arrays.equals(firstArray, secondArray);

    }

    public static void main(String[] args) {

        System.out.println(
                isAnagram("Dormitory", "Dirty Room"));

    }

}

Output

true

Unicode Considerations

Java stores text using Unicode.

Examples

こんにちは

नमस्ते

😊😊

The frequency-array solution in this article assumes an ASCII-based character set.

For international applications, prefer:

  • HashMap<Character, Integer>

If your application must correctly process supplementary Unicode characters (such as many emoji), consider iterating over Unicode code points instead of individual char values.

Edge Cases

Input 1 Input 2 Expected Output
"" "" true
"a" "a" true
"abc" "abcd" false
"abc" "abd" false
"Listen" "Silent" false (case-sensitive)
"123" "321" true
null null Handle gracefully based on application requirements

Time & Space Complexity

Approach Time Extra Space
Sorting O(n log n) O(n)
Single Frequency Array O(n) O(1)*
HashMap O(n) O(n)
Java Streams O(n log n) O(n)
Two Frequency Arrays + Arrays.equals() O(n) O(1)*

Note: The frequency-array approaches use fixed-size arrays (for example, 256 entries for extended ASCII), so their extra space is considered O(1) relative to the input size.

Comparison of All Approaches

Approach Interview Friendly Performance Unicode Friendly
Sorting ⭐⭐⭐⭐ ⭐⭐⭐ ⭐⭐⭐⭐
Single Frequency Array ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ ⭐⭐
HashMap ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐ ⭐⭐⭐⭐⭐
Java Streams ⭐⭐⭐ ⭐⭐⭐ ⭐⭐⭐⭐
Two Frequency Arrays ⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ ⭐⭐

Common Interview Mistakes

Mistake 1

Not checking string lengths first.

Wrong

Arrays.sort(...)

Correct

if (first.length() != second.length()) {
    return false;
}

Mistake 2

Ignoring uppercase and lowercase characters.

Example

Listen

Silent

Convert both strings.

toLowerCase();

Mistake 3

Ignoring spaces and punctuation.

Example

Dirty Room

Process the string before comparison.

replaceAll("[^a-zA-Z0-9]", "")

Mistake 4

Using == to compare strings.

Wrong

first == second

Correct

first.equals(second)

Mistake 5

Choosing sorting when an O(n) solution is expected.

Mention the frequency-array approach if performance matters.

Interview Follow-up Questions

Q1. Can you solve it without sorting?

Q2. Which solution is the most efficient?

Q3. Can you ignore spaces and punctuation?

Q4. Can you ignore uppercase and lowercase letters?

Q5. How would you support Unicode?

Q6. Can you group multiple anagrams together?

Q7. What is the time complexity of sorting?

Q8. Why is the frequency-array solution faster?

Q9. How would you solve this using HashMap?

Q10. Can you solve it using Java Streams?

Related Problems

  • Group Anagrams
  • Valid Anagram
  • Character Frequency
  • Find Duplicate Characters
  • First Non-Repeating Character
  • Remove Duplicate Characters
  • Reverse String
  • Palindrome String
  • Longest Substring Without Repeating Characters

Key Takeaways

  • Two strings are anagrams if they contain the same characters with identical frequencies.
  • The Sorting approach is easy to understand and ideal for beginners.
  • The Single Frequency Array approach is the preferred interview solution because it runs in O(n) time.
  • HashMap is flexible and works well for larger or Unicode character sets.
  • Java Streams provide a concise functional implementation but are generally not the first choice in coding interviews.
  • Always clarify whether spaces, punctuation, and character case should be ignored.

Frequently Asked Interview Questions

Q1. Which approach is best for interviews?

The Single Frequency Array approach is usually preferred because it provides O(n) time complexity and demonstrates an understanding of character counting.

Q2. Why is sorting slower?

Sorting requires O(n log n) time, while frequency counting scans each string only once, resulting in O(n) time.

Q3. Why use HashMap instead of a frequency array?

A HashMap is more flexible because it supports larger character sets and can be extended to solve frequency-related problems beyond ASCII.

Q4. Can numbers also form anagrams?

Yes.

Example

12345

54321

Both contain the same digits with identical frequencies, so they are anagrams.

Q5. How do you solve the LeetCode "Valid Anagram" problem?

The optimal solution is:

  1. Check the string lengths.
  2. Count the frequency of characters in the first string.
  3. Decrease the frequency using the second string.
  4. Verify that every frequency becomes zero.

This achieves O(n) time complexity.

Interview Tip

If an interviewer asks:

"Check whether two strings are anagrams."

Start with the Sorting approach because it is easy to explain and implement.

Then mention the optimized solution:

  1. Compare the lengths.
  2. Use a frequency array.
  3. Increase counts for the first string.
  4. Decrease counts for the second string.
  5. Verify that all counts return to zero.

Finally, discuss advanced variations such as:

  • Ignoring spaces and punctuation
  • Case-insensitive comparisons
  • Unicode support using HashMap
  • Grouping multiple anagrams

Presenting both the basic and optimized approaches demonstrates strong algorithmic thinking and practical Java interview skills.