Valid Anagram

Difficulty: #easy

This is based off the problem found on leetcode called (Valid Anagram).

It has the following problem text,

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Solutions

Optimal solution

An optimal solution would be to build up two hash maps to store the characters that occur as the key, and the count/number of occurrences of the characters as the value. You could then compare the two hash maps; if equal - then s and t are anagrams of one another. You would have to do an upfront check that both strings are the same length. This limits you to a single iteration over the generated hash maps, instead of looping over both.

The complexity of the solution would be $O(s + t)$ where s and t are the sizes of the input strings. This is for both the time and space complexity.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        countS, countT = {}, {}

        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)

        for key in countS:
            if countS[key] != countT.get(key, 0):
                return False

        return True

Golf code type solution

This is a solution that matches the two hash maps version, but is done with a built in python collection called Counter - this is a fast way to express the same solution (maintaining readability).

from collections import Counter


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

Solution with less space complexity

If you don’t want to use the space required for a hash map, you could then run an in-place sort to order both of your strings and compare them to one another.

Best case scenario, you’d be sorting your strings at $O(n \space log \space n)$ time complexity (Best sort complexity). And this is assuming your sorting algorithm uses something with a roughly $O(1)$ space complexity.

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

Golang solution using hash map with tests

This solution is similar to the initial python solution that makes use of two hash maps to count the number of characters.

solution.go

package main

func isAnagram(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}

	sMap := make(map[byte]int)
	tMap := make(map[byte]int)

	for i := 0; i < len(s); i++ {
		sMap[s[i]]++
		tMap[t[i]]++
	}

	for k, v := range sMap {
		if tMap[k] != v {
			return false
		}
	}

	return true
}

solution_test.go

package main

import "testing"

func TestIsAnagram(t *testing.T) {
	testCases := []struct {
		s    string
		t    string
		want bool
		name string
	}{
		{"listen", "silent", true, "Equal length anagrams"},
		{"anagram", "nagaram", true, "Equal length anagrams"},
		{"hi", "world", false, "Unequal length strings"},
		{"rat", "car", false, "Non-anagrams"},
		{"hello", "hi", false, "Non-anagrams"},
		{"", "", true, "Empty strings"},
		{"a", "a", true, "Single character strings"},
	}

	for _, tc := range testCases {
		t.Run(tc.name, func(t *testing.T) {
			got := isAnagram(tc.s, tc.t)
			if got != tc.want {
				t.Errorf("isAnagram(%q, %q) = %v, want %v", tc.s, tc.t, got, tc.want)
			}
		})
	}
}

You can run the above with go test assuming you’ve created a go module, and have two separate files, solution.go, and solution_test.go.