ToolMight LogoToolMight
EasyArrays & HashingPattern: Frequency CountingPattern: Character Array Bucket

Valid Anagram

Determine whether two strings have the exact same character frequencies. A core problem demonstrating the power of fixed-size frequency buckets over O(n log n) sorting.

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.

Examples & Constraints

Example 1
Input: s = "anagram", t = "nagaram"
Output: true
Explanation: Both strings contain 3 'a's, 1 'g', 1 'm', 1 'n', and 1 'r'.
Example 2
Input: s = "rat", t = "car"
Output: false
Explanation: 'rat' contains 't', which is not in 'car'.
Constraints
  • 1 <= s.length, t.length <= 5 * 10^4
  • s and t consist of lowercase English letters.

Select Approach (2 Solutions)

Sorting Comparison

Time:O(n log n)
Space:O(1) to O(n)

Sort both strings alphabetically and compare if the resulting sorted character sequences are identical.

Time ComplexityO(n log n)

Sorting strings of length N takes O(n log n) using standard comparison sort.

Space ComplexityO(1) to O(n)

Depends on language string mutability and sort implementation.

Underlying algorithmic logic

The Canonical Normalization Mental Model

If two recipes use the exact same ingredients in the exact same quantities, alphabetizing both ingredient lists will produce identical outputs.

  1. Length Check: If s.length != t.length, they cannot be anagrams -> instant O(1) early exit.
  2. Sort: Alphabetize both strings so characters appear in standard ascending order.
  3. Compare: If sorted(s) == sorted(t), return true.

The Engineering Trade-off

While this approach takes only 1 or 2 lines of code in Python and JavaScript, standard comparison sorting requires `O(n log n)` time. Furthermore, in languages where strings are immutable (Java, JS, Python), sorting requires allocating fresh character arrays and strings, consuming O(n) heap memory.

Advantages
  • •Concise implementation
Trade-offs
  • •O(n log n) runtime is sub-optimal compared to O(n) frequency counting

Code Implementations

Copy & paste production-ready solutions for Sorting Comparison in your language of choice

File: solution.py
Python
def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)
if __name__ == "__main__":
    print(f'is_anagram("anagram", "nagaram"): {is_anagram("anagram", "nagaram")}')
    print(f'is_anagram("rat", "car"): {is_anagram("rat", "car")}')
Interactive visualizer available

Understand Hash Table Visually

Visualize key hashing functions, index mapping arrays, and hash collision resolution techniques. Test live edge cases and watch memory state transitions step-by-step.

Launch Hash Table Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyStack
Visualizer

Valid Parentheses

Verify that code brackets (), {}, and [] are properly closed and nested in order. This is the exact algorithm compilers, linters, and IDEs use to detect syntax errors in real-time.

1 approach(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Linear Search

The foundational search algorithm for unsorted collections. Scans elements one by one until a match is found or the list is exhausted.

2 approaches(O(n))
Learn logic