Anagram Checker: verify two strings share the same letters

An interviewer at Bloomberg puts two words on the whiteboard: "listen" and "silent". "Can you tell me if these are anagrams, and more importantly, can you write code that does it in linear time?" This is Anagram Checker, also known as Valid Anagram on other platforms. It's one of the most common easy-level string problems, showing up at Bloomberg, Adobe, Google, Amazon, and dozens of other companies. The problem tests whether you understand character frequency analysis and can choose the right data structure for the job.

TL;DR

Compare character frequencies using a fixed-size array of 26 integers (one per lowercase letter). Walk through both strings simultaneously, incrementing the count for each character in the first string and decrementing for the second. If all counts are zero at the end, the strings are anagrams. This runs in O(n) time and O(1) space.

The Problem

Given two strings s and t, determine whether t is an anagram of s. Return true if it is, false otherwise.

Both strings consist of lowercase English letters and have lengths between 1 and 50,000.

isAnagram("anagram", "nagaram") => true
isAnagram("rat", "car")         => false

Two strings are anagrams when they contain exactly the same characters with the same frequencies, just in a different arrangement. "listen" and "silent" are anagrams. "rat" and "car" are not, because "rat" has a 't' while "car" has a 'c'.

Two Approaches

There are two standard ways to solve this. Both are worth knowing.

Approach 1: Sort and Compare

Sort both strings alphabetically. If the sorted versions match, the originals are anagrams.

This works because sorting normalizes any rearrangement. Two strings with the same characters will always sort to the same result. The downside is time: sorting takes O(n log n), which is slower than necessary for this problem.

Approach 2: Character Counting (Optimal)

Instead of sorting, count character frequencies directly. Create an array of 26 zeros (one slot for each letter). For each position in the strings, add 1 for the character in s and subtract 1 for the character in t. If every count ends at zero, the strings have identical character distributions.

This is the approach interviewers expect. It runs in O(n) time with O(1) space.

Walking Through the Algorithm

Step 0: Check Lengths

Before counting anything, verify the strings have the same length. Different lengths make an anagram impossible.

This O(1) check eliminates a class of invalid inputs immediately.

Valid Case: "abc" vs "bac"

Both strings have length 3, so we proceed to counting. We process one character from each string at every index:

At index 0, 'a' from s increments count[a] to +1, while 'b' from t decrements count[b] to -1. At index 1, those counts cancel out. By the end, every count is zero, confirming the anagram.

Invalid Case: "rat" vs "car"

Same length, so we proceed to counting:

After processing all characters, count[c] is -1 and count[t] is +1. The non-zero entries mean 't' appears in s but not t, and 'c' appears in t but not s. Not an anagram.

Implementation

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

import java.util.*;

public class Solution {
  public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
      return false;
    }

    int[] charCount = new int[26];

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

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

    return true;
  }
}

The expression s.charAt(i) - 'a' maps each lowercase letter to an index: 'a' becomes 0, 'b' becomes 1, through 'z' at 25. This avoids the overhead of a hash map while still providing O(1) lookup.

The single-pass increment/decrement pattern is a common technique for comparing two frequency distributions without building two separate maps.

Complexity Analysis

Time: O(n)

The algorithm makes one pass through both strings (O(n)) plus one pass through the 26-element count array (O(1)). The length check is O(1). Total: O(n).

The sorting approach would be O(n log n) due to the sort step. For strings up to 50,000 characters, the difference is measurable.

Space: O(1)

The count array uses 26 integers regardless of input size. Since the alphabet is fixed, this is constant space.

If the problem allowed Unicode characters, you would need a hash map instead, bringing space to O(k) where k is the number of distinct characters. The constraint to lowercase English letters is what makes the array approach both possible and optimal.

Sorting vs. Counting: When to Use Each

In an interview, mention both approaches and explain why you're choosing the counting method. If the problem involves arbitrary Unicode strings and simplicity matters more than speed, sorting is a reasonable fallback.

Common Mistakes

1. Forgetting the length check. Without it, the counting loop works but misses cases where one string is longer. For example, "abc" vs "abcd" would show all counts as zero through index 2, but index 3 would cause an out-of-bounds error in the simultaneous iteration approach.

2. Using a hash map when an array suffices. With lowercase English letters only, a hash map adds unnecessary overhead. The 26-element array is faster and simpler.

3. Incrementing both strings in the same direction. If you increment for both s and t, you end up with combined frequencies rather than a difference. The increment/decrement pattern is what makes the single-array approach work.

4. Returning true too early. Some candidates return true inside the counting loop. The check for all-zeros must happen after processing every character.

Interview Tips

• Clarify the character set first. "Are the strings limited to lowercase English letters?" This tells the interviewer you're thinking about the data structure choice.
• Mention both approaches. Sorting is O(n log n), counting is O(n). Implement counting.
• Explain the - 'a' trick. Subtracting the ASCII value of 'a' maps lowercase letters to indices 0-25. This is a standard pattern the interviewer expects you to know.
• Walk through a short example. Pick "abc" / "bac" and show how the count array changes at each step. This demonstrates you understand the algorithm, not just the code.
• Mention the follow-up. If asked how to handle Unicode, say "I'd replace the array with a HashMap." This shows you understand the tradeoff between the specialized and general solutions.

Related Problems

The character frequency technique from this problem appears in several harder problems:

• Group Anagrams - Sort or hash character frequencies to group strings that are anagrams of each other.
• Find All Anagrams in a String - Sliding window over a longer string, maintaining a running frequency count.
• Minimum Steps to Make Two Strings Anagram - Count the frequency difference and sum the positive values.
• Ransom Note - Check if one string's characters are a subset of another's frequencies.

Once you're comfortable with the count array pattern here, these follow-ups become variations on the same idea with different termination conditions or windowing strategies.

Firecode sequences these problems using spaced repetition so you encounter each pattern right before you'd otherwise forget it. Over 50,000 engineers have used it to prepare for interviews at top tech companies.

Solutions in Other Languages

Python

Python uses a list instead of an array and ord() for character-to-integer conversion.

class Solution:
    def is_anagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        char_count = [0] * 26

        for i in range(len(s)):
            char_count[ord(s[i]) - ord('a')] += 1
            char_count[ord(t[i]) - ord('a')] -= 1

        for count in char_count:
            if count != 0:
                return False

        return True

JavaScript

class Solution {
  isAnagram(s, t) {
    if (s.length !== t.length) {
      return false;
    }

    const charCount = new Array(26).fill(0);

    for (let i = 0; i < s.length; i++) {
      charCount[s.charCodeAt(i) - 97]++;
      charCount[t.charCodeAt(i) - 97]--;
    }

    for (let count of charCount) {
      if (count !== 0) {
        return false;
      }
    }

    return true;
  }
}

TypeScript

class Solution {
  isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) {
      return false;
    }

    const charCount: number[] = new Array(26).fill(0);

    for (let i = 0; i < s.length; i++) {
      charCount[s.charCodeAt(i) - 97]++;
      charCount[t.charCodeAt(i) - 97]--;
    }

    for (const count of charCount) {
      if (count !== 0) {
        return false;
      }
    }

    return true;
  }
}

C++

#include <string>

class Solution {
public:
  bool isAnagram(std::string &s, std::string &t) {
    if (s.length() != t.length()) {
      return false;
    }

    int charCount[26] = {0};

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

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

    return true;
  }
};

Go

func (sol *Solution) IsAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    var charCount [26]int

    for i := 0; i < len(s); i++ {
        charCount[s[i]-'a']++
        charCount[t[i]-'a']--
    }

    for _, count := range charCount {
        if count != 0 {
            return false
        }
    }

    return true
}

Scala

class Solution {
  def isAnagram(s: String, t: String): Boolean = {
    if (s.length != t.length) {
      return false
    }

    val charCount = Array.fill(26)(0)

    for (i <- 0 until s.length) {
      charCount(s(i) - 'a') += 1
      charCount(t(i) - 'a') -= 1
    }

    charCount.forall(_ == 0)
  }
}

Kotlin

class Solution {
  fun isAnagram(s: String, t: String): Boolean {
    if (s.length != t.length) {
      return false
    }

    val charCount = IntArray(26)

    for (i in 0 until s.length) {
      charCount[s[i] - 'a']++
      charCount[t[i] - 'a']--
    }

    for (count in charCount) {
      if (count != 0) {
        return false
      }
    }

    return true
  }
}

Swift

import Foundation

class Solution {
    func isAnagram(_ s: String, _ t: String) -> Bool {
        if s.count != t.count {
            return false
        }

        var charCount = [Int](repeating: 0, count: 26)
        let sChars = Array(s)
        let tChars = Array(t)

        for i in 0..<sChars.count {
            charCount[Int(sChars[i].asciiValue! - Character("a").asciiValue!)] += 1
            charCount[Int(tChars[i].asciiValue! - Character("a").asciiValue!)] -= 1
        }

        for count in charCount {
            if count != 0 {
                return false
            }
        }

        return true
    }
}

Rust

impl Solution {
    pub fn is_anagram(&self, s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false;
        }

        let mut char_count = [0i32; 26];

        for (sb, tb) in s.bytes().zip(t.bytes()) {
            char_count[(sb - b'a') as usize] += 1;
            char_count[(tb - b'a') as usize] -= 1;
        }

        char_count.iter().all(|&c| c == 0)
    }
}

C#

public class Solution {
    public bool isAnagram(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }

        int[] charCount = new int[26];

        for (int i = 0; i < s.Length; i++) {
            charCount[s[i] - 'a']++;
            charCount[t[i] - 'a']--;
        }

        foreach (int count in charCount) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }
}

Dart

class Solution {
  bool isAnagram(String s, String t) {
    if (s.length != t.length) {
      return false;
    }

    List<int> charCount = List<int>.filled(26, 0);

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

    for (int count in charCount) {
      if (count != 0) {
        return false;
      }
    }

    return true;
  }
}

PHP

class Solution {
    public function isAnagram(string $s, string $t): bool {
        if (strlen($s) !== strlen($t)) {
            return false;
        }

        $charCount = array_fill(0, 26, 0);

        for ($i = 0; $i < strlen($s); $i++) {
            $charCount[ord($s[$i]) - ord('a')]++;
            $charCount[ord($t[$i]) - ord('a')]--;
        }

        foreach ($charCount as $count) {
            if ($count !== 0) {
                return false;
            }
        }

        return true;
    }
}

Ruby

class Solution
  def anagram?(s, t)
    return false if s.length != t.length

    char_count = Array.new(26, 0)

    (0...s.length).each do |i|
      char_count[s[i].ord - 'a'.ord] += 1
      char_count[t[i].ord - 'a'.ord] -= 1
    end

    char_count.all? { |count| count == 0 }
  end
end