Valid Anagram

Difficulty: Easy | Acceptance: 68.10% | Paid: No Topics: Hash Table, String, Sorting

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
• Approach 1: Sorting
• Approach 2: Frequency Array
• Approach 3: Hash Map

Examples

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⁴
s and t consist of lowercase English letters.

Approach 1: Sorting

Intuition If two strings are anagrams, they must consist of the exact same characters in the same frequencies. Therefore, sorting both strings will result in identical sequences of characters.

Steps

• Convert both strings to character arrays (or lists).
• Sort both arrays.
• Compare the sorted arrays for equality.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

Complexity

• Time: O(n log n) due to the sorting algorithm, where n is the length of the strings.
• Space: O(1) if we ignore the space required for the output (sorting in place for arrays), or O(n) if the language creates new strings/arrays during the sort process.
• Notes: Simple to implement but not the most efficient in terms of time complexity.

Approach 2: Frequency Array

Intuition Since the problem states that the strings consist only of lowercase English letters, we can use a fixed-size array of length 26 to count the frequency of each character. We increment the count for characters in s and decrement for characters in t. If the strings are anagrams, all counts should be zero at the end.

Steps

• Initialize an integer array of size 26 with zeros.
• Iterate through string s and increment the corresponding index for each character.
• Iterate through string t and decrement the corresponding index for each character.
• Check if all values in the array are zero.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        counts = [0] * 26
        for c in s:
            counts[ord(c) - ord('a')] += 1
        
        for c in t:
            counts[ord(c) - ord('a')] -= 1
            if counts[ord(c) - ord('a')] < 0:
                return False
                
        return True

Complexity

• Time: O(n) since we traverse the strings once.
• Space: O(1) because the array size is fixed (26) regardless of input size.
• Notes: This is the most optimal solution for this specific problem given the constraint of lowercase English letters.

Approach 3: Hash Map

Intuition If the character set were not limited to lowercase English letters (e.g., Unicode characters), a fixed-size array would not be feasible. A Hash Map (or Dictionary) allows us to store frequencies for any arbitrary character.

Steps

• Create an empty hash map.
• Iterate through string s, storing the count of each character in the map.
• Iterate through string t:
  • If a character is not in the map or its count is zero, return false.
  • Otherwise, decrement the count in the map.
• If the loop finishes, return true.

from collections import defaultdict

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        count = defaultdict(int)
        for c in s:
            count[c] += 1
        
        for c in t:
            if count[c] == 0:
                return False
            count[c] -= 1
            
        return True

Complexity

• Time: O(n) to traverse the strings.
• Space: O(k) where k is the number of unique characters in the strings.
• Notes: More flexible than the frequency array approach but has slightly higher constant overhead due to hashing.