Are these strings anagrams?

You're ten minutes into a Microsoft phone screen, and the interviewer asks: "Given two strings, can you tell me if they're anagrams of each other?" It sounds simple enough. "Binary" and "brainy" use the exact same letters, just shuffled around. But the follow-up is what separates candidates: "Can you do it in linear time?" This problem, also known as "Valid Anagram" on other platforms, is a staple warm-up question that tests your ability to think in terms of frequency counting, a technique that shows up in dozens of harder problems down the line.

TL;DR

Build a character frequency map from the first string (incrementing counts), then walk through the second string (decrementing counts). If every count lands back at zero, the strings are anagrams. The approach runs in O(n) time and O(n) space, and handles case insensitivity by converting both strings to uppercase before processing.

Why This Problem Matters

Anagram checking is one of those interview questions that punches above its weight. On the surface, it's straightforward. Underneath, it's testing whether you can reach for a hash map instead of brute-forcing with nested loops or sorting. The frequency-counting pattern you learn here transfers directly to problems like grouping anagrams, finding minimum window substrings, and checking string permutations. Get comfortable with this pattern and you'll recognize it everywhere.

What Is an Anagram?

An anagram of a string is another string that uses every character from the original exactly once, rearranged in any order. "Listen" and "silent" are anagrams. "Hello" and "world" are not.

For this problem, comparisons are case-insensitive, so "Cat" and "Act" count as anagrams. Both strings use {A: 1, C: 1, T: 1} when you normalize to uppercase.

Understanding the Problem

Let's pin down the requirements:

Given: Two strings, s1 and s2 Return: true if they are anagrams, false otherwise Constraints: Case-insensitive comparison, en-us locale

Here are a few examples:

isPairAnagram("binary", "brainy") -> true
isPairAnagram("Cat", "Act")       -> true
isPairAnagram("cool", "look")     -> false

Edge Cases Worth Thinking About

1. Two empty strings: Both have zero characters, so they're trivially anagrams
2. Different lengths: Can never be anagrams (useful as an early exit)
3. Single characters with different cases: "A" and "a" are anagrams
4. Strings with spaces: "eleven plus two" and "twelve plus one" are anagrams if spaces are treated as characters

The Sorting Shortcut (and Why It's Not Optimal)

A natural first instinct: sort both strings and compare. If the sorted versions match, they're anagrams.

// Sorting approach - O(n log n)
char[] arr1 = s1.toUpperCase().toCharArray();
char[] arr2 = s2.toUpperCase().toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
return Arrays.equals(arr1, arr2);

This works, but sorting costs O(n log n). We can do better.

Solution Approach: Character Frequency Map

The key insight is that two strings are anagrams if and only if every character appears the same number of times in both. Instead of sorting, we count.

Here's the plan:

1. Create a hash map to store character frequencies
2. Walk through s1, incrementing the count for each character
3. Walk through s2, decrementing the count for each character
4. If all counts are zero, the strings are anagrams

Prefer a different language? Jump to solutions in other languages.

Tracing Through an Example

Let's trace isPairAnagram("Cat", "Act"). Both strings get uppercased first, so we're working with "CAT" and "ACT".

Pass 1: Increment counts from "CAT"

After processing s1, the map holds {C: 1, A: 1, T: 1}. Each character appeared once.

Pass 2: Decrement counts from "ACT"

Every count drops back to zero. The strings are anagrams.

When It Fails: "cool" vs "look"

Let's see what happens with a pair that is not an anagram:

After processing "LOOK" against the counts from "COOL", we end up with C: 1 and K: -1. These non-zero values immediately tell us the strings differ in their character makeup.

Implementation

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

public class Solution {
  public Boolean isPairAnagram(String s1, String s2) {
    // Create a HashMap to track character counts
    Map<Character, Integer> countsMap = new HashMap<>();

    // Increment counts for each character in s1 (uppercased)
    s1.toUpperCase().chars().forEach(c -> countsMap.put(
      (char) c,
      countsMap.getOrDefault((char) c, 0) + 1
    ));

    // Decrement counts for each character in s2 (uppercased)
    s2.toUpperCase().chars().forEach(c -> countsMap.put(
      (char) c,
      countsMap.getOrDefault((char) c, 0) - 1
    ));

    // If all values are 0, the strings are anagrams
    return countsMap
             .values()
             .stream()
             .filter(n -> n != 0)
             .findAny()
             .isEmpty();
  }
}

A few things to notice about this implementation:

• toUpperCase() handles case insensitivity before we touch the map
• getOrDefault avoids null checks when a character hasn't been seen yet
• The final stream filters for any non-zero value. If none exist, the strings are anagrams
• We use a single map rather than two separate maps, which keeps the logic clean

Why One Map Instead of Two?

You could build a frequency map for each string and then compare them entry by entry. That works, but it doubles your code and requires an explicit comparison loop. With the single-map approach, the increment/decrement pattern naturally cancels matching characters, and the final zero-check is a single pass over the map values.

Complexity Analysis

Time Complexity: O(n)

We make two linear passes through the input strings, one for incrementing and one for decrementing. Each hash map operation (put, getOrDefault) runs in O(1) amortized time. The final check iterates over the map values, which is bounded by the number of distinct characters (at most 26 for English letters, or the full character set for Unicode). Total: O(n) where n is the combined length of both strings.

Space Complexity: O(n)

The hash map stores at most one entry per distinct character. For English letters this is bounded by 26, making it effectively O(1). For arbitrary Unicode strings, the map could grow to O(n) in the worst case where every character is unique.

Comparison with Sorting

If you know the input is limited to lowercase English letters, you can replace the hash map with an int[26] array for true O(1) space. But the hash map solution is more general and what interviewers typically expect.

Common Pitfalls

1. Forgetting case normalization: Without .toUpperCase(), "Cat" and "act" would return false. Always normalize before comparing.

2. Using character subtraction on different-length strings: The algorithm handles this naturally since extra characters in the longer string will leave non-zero counts. But adding a length check as an early exit is a nice optimization:

   if (s1.length() != s2.length()) return false;
   

3. Assuming ASCII only: If the interviewer mentions Unicode or special characters, mention that your hash map approach handles them without modification, unlike a fixed-size array.

4. Overcomplicating the final check: Some candidates build a second loop to check counts manually. Using streams or a built-in allMatch/every keeps the code concise.

Interview Tips

When you encounter this problem in an interview:

1. Start by restating the definition: "An anagram uses all characters from the original string exactly once, in any order." This shows you understand the problem.

2. Mention the sorting approach first, then optimize: Interviewers like seeing you consider multiple solutions. Say "I could sort both strings in O(n log n), but I can do better with a hash map in O(n)."

3. Ask about case sensitivity and character set: These aren't just pedantic questions. They affect your implementation. Case-insensitive comparison needs .toUpperCase(). A known character set enables array-based optimization.

4. Draw the map state: Sketch the counts map after processing each character. This makes your logic visible and catches bugs early.

5. Handle follow-ups confidently: "What if you need to check millions of pairs against the same string?" (Pre-compute the frequency map.) "What about grouping anagrams?" (Use sorted string or frequency signature as a hash key.)

Key Takeaways

• The character frequency map pattern solves anagram checking in O(n) time by incrementing counts for one string and decrementing for the other, then verifying all counts are zero.
• Always normalize case before comparing. A single .toUpperCase() call prevents subtle bugs with mixed-case inputs like "Cat" and "act".
• One map with increment/decrement is cleaner and more efficient than two separate maps with a comparison step.
• This frequency-counting technique is foundational. It reappears in problems like grouping anagrams, minimum window substring, and permutation checking.
• For known character sets (e.g., lowercase English), swap the hash map for an int[26] array to achieve O(1) space. Mention this optimization in interviews to show depth.

Related Problems and Next Steps

Once you're comfortable with basic anagram checking, push yourself with these related challenges:

• Group anagrams together from a list of strings (uses frequency signatures as hash keys)
• Find all anagram substrings of a pattern within a larger string (sliding window + frequency map)
• Check if a string is a permutation of a palindrome (frequency counting with an odd-count check)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Whether this is your first algorithm problem or your hundredth, building fluency with patterns like frequency counting is what separates candidates who pass from those who don't.

Solutions in Other Languages

Python

class Solution:
    def is_pair_anagram(self, s1: str, s2: str) -> bool:
        counts_map = {}

        for c in s1.upper():
            counts_map[c] = counts_map.setdefault(c, 0) + 1

        for c in s2.upper():
            counts_map[c] = counts_map.setdefault(c, 0) - 1

        return all(value == 0 for value in counts_map.values())

JavaScript

class Solution {
  isPairAnagram(s1, s2) {
    const countsMap = new Map();

    [...s1.toUpperCase()].forEach(c => {
      countsMap.set(c, countsMap.get(c) === undefined ? 1 : countsMap.get(c) + 1);
    });

    [...s2.toUpperCase()].forEach(c => {
      countsMap.set(c, countsMap.get(c) === undefined ? -1 : countsMap.get(c) - 1);
    });

    return [...countsMap.values()].find(v => v !== 0) === undefined;
  }
}

TypeScript

class Solution {
  isPairAnagram(s1: string, s2: string): boolean {
    const countsMap = new Map<string, number>();

    [...s1.toUpperCase()].forEach(c => {
      countsMap.set(c, (countsMap.get(c) ?? 0) + 1);
    });

    [...s2.toUpperCase()].forEach(c => {
      countsMap.set(c, (countsMap.get(c) ?? 0) - 1);
    });

    return [...countsMap.values()].every(v => v === 0);
  }
}

C++

#include <map>
#include <cctype>
#include <algorithm>

class Solution {
public:
  bool isPairAnagram(std::string s1, std::string s2) {
    std::map<char, int> countsMap;

    for (auto c : s1)
      countsMap[toupper(c)] += 1;

    for (auto c : s2)
      countsMap[toupper(c)] -= 1;

    return std::all_of(countsMap.begin(), countsMap.end(),
                       [](auto entry) { return entry.second == 0; });
  }
};

Scala

import scala.collection.mutable

class Solution {
  def isPairAnagram(s1: String, s2: String): Boolean = {
    val countsMap = mutable.Map[Char, Int]()

    s1.toUpperCase.foreach { c =>
      countsMap.put(c, countsMap.get(c).map(_ + 1).getOrElse(1))
    }

    s2.toUpperCase.foreach { c =>
      countsMap.put(c, countsMap.get(c).map(_ - 1).getOrElse(-1))
    }

    !countsMap.values.exists(_ != 0)
  }
}

Kotlin

class Solution {
  fun isPairAnagram(s1: String, s2: String): Boolean {
    val countsMap = mutableMapOf<Char, Int>()

    s1.uppercase().forEach { c ->
      countsMap[c] = countsMap.getOrDefault(c, 0) + 1
    }

    s2.uppercase().forEach { c ->
      countsMap[c] = countsMap.getOrDefault(c, 0) - 1
    }

    return countsMap.values.none { it != 0 }
  }
}

Swift

import Foundation

class Solution {
    func isPairAnagram(_ s1: String, _ s2: String) -> Bool {
        var countsMap = [Character: Int]()

        for c in s1.uppercased() {
            countsMap[c, default: 0] += 1
        }

        for c in s2.uppercased() {
            countsMap[c, default: 0] -= 1
        }

        return countsMap.values.allSatisfy { $0 == 0 }
    }
}

Rust

use std::collections::HashMap;

impl Solution {
    pub fn is_pair_anagram(&self, s1: String, s2: String) -> bool {
        let mut counts_map: HashMap<char, i32> = HashMap::new();

        for c in s1.to_uppercase().chars() {
            *counts_map.entry(c).or_insert(0) += 1;
        }

        for c in s2.to_uppercase().chars() {
            *counts_map.entry(c).or_insert(0) -= 1;
        }

        counts_map.values().all(|&v| v == 0)
    }
}

Ruby

class Solution
  def is_pair_anagram(s1, s2)
    counts_hash = {}

    s1.upcase.chars.each { |c| counts_hash[c] = (counts_hash[c] || 0) + 1 }

    s2.upcase.chars.each { |c| counts_hash[c] = (counts_hash[c] || 0) - 1 }

    counts_hash.values.all? { |v| v == 0 }
  end
end

Dart

class Solution {
  bool isPairAnagram(String s1, String s2) {
    Map<String, int> countsMap = {};

    for (String c in s1.toUpperCase().split('')) {
      countsMap[c] = (countsMap[c] ?? 0) + 1;
    }

    for (String c in s2.toUpperCase().split('')) {
      countsMap[c] = (countsMap[c] ?? 0) - 1;
    }

    return countsMap.values.every((v) => v == 0);
  }
}

PHP

class Solution {
    public function isPairAnagram(string $s1, string $s2): bool {
        $countsMap = [];

        foreach (str_split(strtoupper($s1)) as $char) {
            $countsMap[$char] = ($countsMap[$char] ?? 0) + 1;
        }

        foreach (str_split(strtoupper($s2)) as $char) {
            $countsMap[$char] = ($countsMap[$char] ?? 0) - 1;
        }

        return count(array_filter($countsMap, fn($v) => $v !== 0)) === 0;
    }
}

C#

using System.Collections.Generic;
using System.Linq;

public class Solution {
    public bool isPairAnagram(string s1, string s2) {
        var countsMap = new Dictionary<char, int>();

        foreach (char c in s1.ToUpper()) {
            countsMap[c] = countsMap.GetValueOrDefault(c, 0) + 1;
        }

        foreach (char c in s2.ToUpper()) {
            countsMap[c] = countsMap.GetValueOrDefault(c, 0) - 1;
        }

        return countsMap.Values.All(v => v == 0);
    }
}