Valid Anagram in Python: Three Solutions and the Follow-Up Question That Catches People

By Pooja Goenka · Published 2026-10-21

Two strings are anagrams if one is a rearrangement of the other, which means they contain the same characters with the same counts. In Python the shortest correct check is sorted(s) == sorted(t), which runs in O(n log n). Counting the characters instead runs in O(n), and there are two ways to count: a hash map (collections.Counter) or a fixed array of 26 slots. The array version is fastest, and it hides a bug that this post demonstrates.

Here is the short version:

• Sort both strings and compare: three lines, O(n log n) time.
• Count with Counter and compare: O(n) time, works on any characters.
• Count with a 26-slot array: O(n) time and constant extra space, but only for lowercase a to z.
• Compare lengths first. Different lengths can never be anagrams, and it saves work.
• The usual follow-up is "what if the input has Unicode?" Answer it before the interviewer asks.

The problem is Valid Anagram, a standard easy question on most DSA lists. The statement: given strings s and t, return true if t is an anagram of s, and false otherwise. For example, "triangle" and "integral" use the same eight letters once each, so the answer is true. "rat" and "car" are not, so the answer is false.

Solution 1: sort both and compare

def is_anagram_sort(s, t):
    return sorted(s) == sorted(t)

If two strings are rearrangements of each other, sorting puts their characters in the same order, so the sorted lists are equal. Sorting costs O(n log n) time, and the sorted lists take O(n) extra space.

This is the answer I would give first in an interview, because it is obviously correct and takes a minute to write. It also leaves a clear opening. The next sentence is "I can do better than n log n by counting."

Solution 2: count with a hash map

from collections import Counter

def is_anagram_counter(s, t):
    return Counter(s) == Counter(t)

Counter builds a dictionary mapping each character to how many times it appears. Two strings are anagrams exactly when their count dictionaries are equal. Building each one is O(n), and comparing them is bounded by the number of distinct characters, so the whole thing is O(n) time. Extra space is O(k), where k is the number of distinct characters.

This version needs no assumption about the alphabet. Lowercase, uppercase, digits, emoji, Chinese characters: it counts whatever it is given. Of the three solutions it is the one I would ship.

Solution 3: count with a 26-slot array

When the problem promises lowercase English letters only, you can replace the dictionary with a list of 26 integers, one slot per letter. Add one for each character of s, subtract one for each character of t, and the strings are anagrams if every slot ends at zero.

def is_anagram_array(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26
    for a, b in zip(s, t):
        counts[ord(a) - ord("a")] += 1
        counts[ord(b) - ord("a")] -= 1
    return not any(counts)

ord("a") is 97, so ord(a) - 97 maps "a" to slot 0, "b" to slot 1, and so on to "z" at slot 25. The loop is O(n), the final check looks at 26 slots, and the extra space is a list of 26 integers whatever the input size, so O(1).

This is the solution most tutorials stop at. I ran all three against the same test cases, including empty strings, strings of unequal length, and "aacc" against "ccac", and they agree. On valid input they behave the same.

The bug in the array version

Now try input the problem did not promise.

is_anagram_array("A", "a")    # IndexError: list index out of range
is_anagram_array("[", "u")    # True

The first call fails loudly, which is the better outcome. "A" has an ord of 65, so the slot number is 65 - 97 = -32, outside a 26-slot list.

The second call is worse. The character "[" has an ord of 91, and 91 - 97 is -6. Python lets you index a list from the end with negative numbers, so counts[-6] quietly means slot 20, which is the slot for "u". The function sees "[" and "u" as the same character and returns True for two strings that are not anagrams. No error, no warning.

The lesson is general. A fixed-size array turns an assumption about the input into silent wrong answers when the assumption breaks, and a language with negative indexing can make that quiet instead of loud. If the problem says lowercase only, you may rely on it. If you are writing code for real data, validate or use Counter.

The Unicode follow-up

Interviewers often ask: "What if the strings contain Unicode characters?" The expected answer is to swap the array for a hash map, which is Solution 2, and to state why: the array's size is tied to a 26-letter alphabet, and a hash map's size is tied to the number of distinct characters present.

There is a second layer, which you can mention if you know it. Some characters can be written in more than one way. An accented letter may be a single code point or a base letter followed by a combining mark, and Python compares those as different strings even though they display the same. If that matters, normalise both strings first with unicodedata.normalize("NFC", s) before counting. Whether it matters depends on the problem, so ask.

Comparing the three

In this table n is the length of the string and k is the number of distinct characters. For ordinary English words, all three finish instantly, so the choice is about clarity and correctness. The O(1) space claim only counts the array. The sorted version copies the strings and the Counter version stores a dictionary, so those numbers are real.

Variations worth practising

• Group Anagrams: given a list of words, group the ones that are anagrams of each other. A sorted word, or a tuple of 26 counts, works as a dictionary key.
• Find All Anagrams in a String: a sliding window with the counting trick, updating the counts as the window moves.
• Ransom Note: the same counting idea, with a one-directional check.

If you can explain why the counting idea carries across all four, you have the pattern and not only the answer.

Where LogicWiz fits

LogicWiz has a free Valid Anagram practice page with an in-browser editor, auto-judging and step-wise hints, plus a guided walkthrough from the sort approach to the 26-slot array. If you want the same habit across other problems, free ways to learn and practise DSA, compared covers what else is available, including tools that are not ours.

Common questions

What is the time complexity of Valid Anagram?

Sorting both strings is O(n log n). Counting characters with a dictionary or a fixed array is O(n). A length check first lets you return False immediately for strings of different lengths.

Is the 26-slot array solution O(1) space?

Yes, if the alphabet is fixed at 26 letters, because the array does not grow with the input. If the input can contain any character, you need a dictionary, and the space grows with the number of distinct characters.

How do you check for an anagram in Python in one line?

sorted(s) == sorted(t), or Counter(s) == Counter(t) after from collections import Counter. The second is usually faster on long strings.

Does Valid Anagram care about case and spaces?

The standard problem uses lowercase letters only, so it does not. For real text you decide: lowercase both strings, strip spaces and punctuation, then compare. Say which rules you chose out loud in an interview.

What if the strings contain Unicode?

Use a hash map instead of a fixed array. If visually identical characters can have different encodings, normalise both strings with unicodedata.normalize before counting.