Valid Anagram is a classic string problem that teaches different ways to compare the frequency of characters in two strings. While the problem is simple, it introduces an important concept you’ll use repeatedly in coding interviews: counting occurrences efficiently.

In this post, we’ll explore three different Python solutions, understand how they work, and compare their time and space complexities.

Problem

Given two strings s and t, return True if t is an anagram of s; otherwise, return False.

An anagram is a word or phrase formed by rearranging the letters of another word, using exactly the same charactersthe same number of times.

Example 1

Input:
s = "racecar"
t = "carrace"

Output:
True

Example 2

Input:
s = "jar"
t = "jam"

Output:
False

Constraints

• 1 <= s.length, t.length <= 5 × 10⁴
• Both strings contain only lowercase English letters.

Solution 1: Sort Both Strings

The simplest approach is to sort both strings and compare them.

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

        return sorted(s) == sorted(t)

How it works

If two strings are anagrams, sorting them will produce the same sequence of characters.

For example:

s = "racecar"
sorted(s) = ['a', 'a', 'c', 'c', 'e', 'r', 'r']

t = "carrace"
sorted(t) = ['a', 'a', 'c', 'c', 'e', 'r', 'r']

Since the sorted results are identical, the strings are anagrams.

Complexity

• Time: O(n log n)
• Space: O(n) (Python’s sorting creates new lists)

Pros

• Very easy to write.
• Easy to understand.

Cons

• Sorting is more expensive than necessary.
• Not the optimal solution.

Solution 2: Count Characters with Dictionaries

Instead of sorting, we can count how many times each character appears.

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)

        return countS == countT

How it works

We build two frequency maps.

Example:

s = "listen"

{
    'l': 1,
    'i': 1,
    's': 1,
    't': 1,
    'e': 1,
    'n': 1
}

If both dictionaries contain the same keys with the same counts, the strings are anagrams.

Complexity

• Time: O(n)
• Space: O(1)*

*Although we’re using dictionaries, the input only contains lowercase English letters. That means the dictionaries can hold at most 26 keys, so the extra space is constant.

Pros

• Optimal time complexity.
• Easy to explain in interviews.
• Works for any character set with only minor modifications.

Solution 3: Fixed-Size Array (Most Efficient)

Since the problem only contains lowercase English letters (a–z), we can replace dictionaries with an array of size 26.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        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

        for c in count:
            if c != 0:
                return False

        return True

How it works

Each index represents one letter:

Index:  0  1  2 ... 25
Letter: a  b  c ...  z

As we iterate through both strings:

• Increment the count for characters in s.
• Decrement the count for characters in t.

If the strings are anagrams, every increment will be canceled out by a corresponding decrement.

Example:

s = "abc"
t = "cab"

After processing:

a → +1 -1 = 0
b → +1 -1 = 0
c → +1 -1 = 0

If every value in the array is zero, the strings are anagrams.

Why use ord()?

ord() converts a character into its ASCII (Unicode) value.

For example:

ord('a')  # 97
ord('b')  # 98
ord('c')  # 99

Subtracting ord('a') gives us a zero-based index:

ord('a') - ord('a') = 0
ord('b') - ord('a') = 1
ord('z') - ord('a') = 25

This lets us map every lowercase letter directly to an array index.

Complexity

• Time: O(n)
• Space: O(1)

Pros

• Fastest solution.
• Constant extra space.
• Common interview optimization when the character set is fixed.

Cons

• Only works when the range of possible characters is known in advance.
• Slightly less readable than the dictionary solution.

Complexity Comparison

*The dictionary stores at most 26 lowercase English letters, so its space usage is constant for this problem.

Key Takeaways

This problem demonstrates several ways to solve the same task, each improving on the previous one.

• Sorting is simple and intuitive but slower because of the sorting step.
• Dictionaries count character frequencies in linear time and are flexible enough to handle larger character sets.
• A fixed-size array is the most efficient solution when the possible characters are limited, such as lowercase English letters.

In coding interviews, it’s perfectly fine to start with the sorting approach. Then, explain how you can optimize it using a frequency map, and finally mention the array optimization when the character set is fixed. Showing this progression demonstrates both problem-solving skills and an understanding of algorithmic trade-offs.