EasyBlind75StringHash Table

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word formed by rearranging the letters of another word.

Examples

Input
s = 'anagram', t = 'nagaram'
Output
true

Both strings contain the same characters with the same frequencies.

Input
s = 'rat', t = 'car'
Output
false

'r' and 'a' in s do not map to 'c' and 'a' in t.

Constraints

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

Approaches

Sort both strings and compare them.

CodeT: O(n log n) | S: O(n)
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Use a fixed-size array of 26 to count character frequencies.

CodeT: O(n) | S: O(1)
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26
    for i in range(len(s)):
        count[ord(s[i]) - ord('a')] += 1
        count[ord(t[i]) - ord('a')] -= 1
    return all(c == 0 for c in count)

Use a hash map to count character frequencies in s, then decrement for t.

Diagram

s='anagram', t='nagaram' count after s: {a:3, n:1, g:1, r:1, m:1} Processing t: all counts become 0 -> True
CodeT: O(n) | S: O(1)
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = {}
    for char in s:
        count[char] = count.get(char, 0) + 1
    for char in t:
        if char not in count:
            return False
        count[char] -= 1
        if count[char] < 0:
            return False
    return True

Complexity Comparison

Sorting
T: O(n log n)S: O(n)

Sort both strings and compare them.

Character Count Array
T: O(n)S: O(1)

Use a fixed-size array of 26 to count character frequencies.

Hash Map
T: O(n)S: O(1)

Use a hash map to count character frequencies in s, then decrement for t.

Common Mistakes

Not checking if lengths are equal first

Using count[s[i]]++ without checking if key exists

Forgetting to check that all counts are zero, not just some

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems