TIC
The Interns Company

Valid Anagram

EasyAcceptance: 62.1%
Hash TableStringSorting

Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constraints:

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

Input Format:

  • Two strings s and t

Output Format:

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

Examples:

Example 1:

Input:

s = "anagram", t = "nagaram"

Output:

true

Explanation:

Both strings contain the same characters with the same frequencies, just in a different order.

Example 2:

Input:

s = "rat", t = "car"

Output:

false

Explanation:

The strings have different characters, so t is not an anagram of s.

Solutions

Hash Map Approach

Time: O(n) where n is the length of the strings
Space: O(k) where k is the size of the character set (26 for lowercase English letters)

Use a hash map to count the frequency of each character in the first string, then decrement the counts using the second string. If all counts are zero at the end, the strings are anagrams.

Sorting Approach

Time: O(n log n) where n is the length of the strings
Space: O(n) or O(1) depending on the sorting implementation

Sort both strings and check if they are identical. If they are, then they are anagrams.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Initialize a hash map for character counts: {}
  2. Count characters in 's':
  3. 'a' appears 3 times: {'a': 3}
  4. 'n' appears 1 time: {'a': 3, 'n': 1}
  5. 'g' appears 1 time: {'a': 3, 'n': 1, 'g': 1}
  6. 'r' appears 1 time: {'a': 3, 'n': 1, 'g': 1, 'r': 1}
  7. 'm' appears 1 time: {'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1}
  8. Check characters in 't':
  9. Decrement count for 'n': {'a': 3, 'n': 0, 'g': 1, 'r': 1, 'm': 1}
  10. Decrement count for 'a': {'a': 2, 'n': 0, 'g': 1, 'r': 1, 'm': 1}
  11. Decrement count for 'g': {'a': 2, 'n': 0, 'g': 0, 'r': 1, 'm': 1}
  12. Decrement count for 'a': {'a': 1, 'n': 0, 'g': 0, 'r': 1, 'm': 1}
  13. Decrement count for 'r': {'a': 1, 'n': 0, 'g': 0, 'r': 0, 'm': 1}
  14. Decrement count for 'a': {'a': 0, 'n': 0, 'g': 0, 'r': 0, 'm': 1}
  15. Decrement count for 'm': {'a': 0, 'n': 0, 'g': 0, 'r': 0, 'm': 0}
  16. All counts are zero, so return true

Hints

Hint 1
Two strings are anagrams if and only if they have the same characters with the same frequencies.
Hint 2
You can use a hash table or array to count character frequencies.
Hint 3
Alternatively, you could sort both strings and check if they are identical.

Video Tutorial

Valid Anagram - Frequency Counter Approach

YouTube•Learn the Valid Anagram solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize how character frequencies are tracked between the two strings to determine if they are anagrams.

Key visualization elements:

  • character frequency count
  • validation process

Similar Questions

Group Anagrams

Medium

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Asked By

AmazonMicrosoftFacebookBloombergUberAppleAdobe

Implementation Notes

This is a classic string manipulation problem that tests understanding of character frequency counting and data structures like hash maps. While the sorting solution is more intuitive, the hash map approach is more efficient.