type
status
date
slug
summary
tags
category
icon
password
Problem Statement
Given two strings s and t, return true if the two strings are anagrams of each other, and false otherwise.
An anagram is a word formed by rearranging the letters of another, using all original letters exactly once.
Examples
Input: s = "racecar", t = "carrace"
Output: true
Input: s = "jar", t = "jam"
Output: false
Constraints:
s and t consist of lowercase English letters.Solutions
1. Sorting Approach
Core Idea:
Anagrams contain the exact same characters in a different order, so sorting both strings should result in the same sequence. Sorting is used because it simplifies the comparison without manually counting characters.
Time Complexity: O(n log n + m log m)
Space Complexity: O(1) or O(n + m)
2. Hash Map Approach
Core Idea:
We count the frequency of each character in both strings and compare the maps. A hash map is chosen because it allows O(1) updates and supports any character set, making it flexible and easy to read.
Time Complexity: O(n + m)
Space Complexity: O(1)
3. Hash Table with Array
Core Idea:
We track character frequencies using a fixed-size array of 26 integers since the input is limited to lowercase letters. This is more space- and time-efficient than a hash map when the key range is known and small.
Time Complexity: O(n + m)
Space Complexity: O(1)
Comparison
Solution | Time Complexity | Space Complexity |
Sorting | O(n log n + m log m) | O(1) or O(n + m) |
Hash Map | O(n + m) | O(1) |
Hash Table (Array) | O(n + m) | O(1) |
Best Practice
The array-based solution is the most optimal when the character set is known and limited, like lowercase letters. The hash map is easier to adapt to other character sets. Sorting is clean and concise, though slightly less efficient.