Valid Anagram

Problem Statement

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Example 1:

Input: s = "racecar", t = "carrace"
Output: true

Example 2:

Input: s = "jar", t = "jam"
Output: false

Constraints:

• s and t consist of lowercase English letters.

You should aim for a solution with O(n + m) time and O(1) space, where n is the length of the string s and m is the length of the string t.

Recommended Time and Space Complexity

You should aim for a solution with O(n + m) time and O(1) space, where n is the length of the string s and m is the length of the string t.

Hint 1

A brute force solution would be to sort the given strings and check for their equality. This would be an O(n log n + m log m) solution. Though this solution is acceptable, can you think of a better way without sorting the given strings?

Hint 2

By the definition of the anagram, we can rearrange the characters. Does the order of characters matter in both the strings? Then what matters?

Hint 3

We can just consider maintaining the frequency of each character. We can do this by having two separate hash tables for the two strings. Then, we can check whether the frequency of each character in string s is equal to that in string t and vice versa.

Solution

Sorting

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    return sorted(s) == sorted(t)

Time complexity: O(n log n + m log m) Space complexity: O(1)