#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/hash-tables/valid-anagram-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/hash-tables/valid-anagram-implementation

Repovive

Valid Anagram - Implementation - Hash Tables | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Valid Anagram - Implementation

Complete solution

Here's the solution using one map:

function isAnagram(s, t)
    if length of s != length of t
        return false

    freq := empty hash map

    for each char in s
        freq[char] := freq[char] + 1  // default 0

    for each char in t
        if char not in freq or freq[char] = 0
            return false
        freq[char] := freq[char] - 1

    return true

Time: $O(n)$ . Space: $O(k)$ where $k$ is the alphabet size.