Coding problem · Easy · Arrays & Hashing

Valid Anagram

Easy Algorithms & data structures Seen at Amazon, Bloomberg, Uber

Given two strings s and t, return true if t is an anagram of s (same letters with the same counts), otherwise false.

Example 1

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

Example 2

Input: s = "rat", t = "car"
Output: false

Constraints

Strings contain lowercase English letters

Hints

Hint 1

Different lengths can never be anagrams.

Hint 2

Count characters of s, then subtract counts for t.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1) — at most 26 letters

Count letters in a map (or a 26-slot array): increment for s, decrement for t. Every count must end at zero. Sorting both strings also works in O(n log n).

Reference solution

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Map();
  for (const c of s) count.set(c, (count.get(c) ?? 0) + 1);
  for (const c of t) {
    if (!count.get(c)) return false;
    count.set(c, count.get(c) - 1);
  }
  return true;
}

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const count = new Array<number>(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++;
    count[t.charCodeAt(i) - 97]--;
  }
  return count.every((n) => n === 0);
}

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

<?php

function isAnagram(string $s, string $t): bool
{
    return strlen($s) === strlen($t) && count_chars($s, 1) == count_chars($t, 1);
}

class Solution {
    public 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 c : count) if (c != 0) return false;
        return true;
    }
}

Follow-up questions

What if the input contains Unicode? (use a map, and consider normalization)