Valid Anagram

242. Valid Anagram

Easy

Return true if t is an anagram of s, and false otherwise.

Hash TableStringSorting

View Problem

Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= s.length, t.length <= 5 * 10^4
• s and t consist of lowercase English letters

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Try It Yourself

TypeScript

function isAnagram(s: string, t: string): boolean {
    // Your solution here
}

Go

func isAnagram(s string, t string) bool {
    // Your solution here
}

Solution

Click to reveal solution

Two main approaches: sorting the characters or counting character frequencies.

TypeScript Solution (Sorting)

function isAnagram(s: string, t: string): boolean {
  return s.split("").toSorted().join("") === t.split("").toSorted().join("");
}

Time:O(n log n)

Space:O(1)

Go Solution (Character Counting)

func isAnagram(s string, t string) bool {
  count := map[rune]int{}

  for _, ch := range s {
      _, ok := count[ch]
      if !ok {
          count[ch] = 0
      }
      count[ch]++
  }

  for _, ch := range t {
      _, ok := count[ch]
      if !ok {
          return false
      }
      count[ch]--
  }

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

  return true
}

Time:O(n)

Space:O(1)

Algorithm (Sorting Approach):

1. Sort both strings character by character
2. Compare if the sorted strings are equal
3. If equal, they are anagrams; otherwise, they are not

Algorithm (Character Counting Approach):

1. Create a frequency map for characters in the first string
2. Iterate through the second string and decrement counts
3. If any character is not found or count goes negative, return false
4. Check if all counts are zero at the end

Alternative TypeScript Solution (Character Counting):

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
    
    const count = new Map<string, number>();
    
    // Count characters in s
    for (const char of s) {
        count.set(char, (count.get(char) || 0) + 1);
    }
    
    // Decrement counts for characters in t
    for (const char of t) {
        if (!count.has(char)) return false;
        count.set(char, count.get(char)! - 1);
        if (count.get(char) === 0) count.delete(char);
    }
    
    return count.size === 0;
}