EasyHash TableStringSorting

Valid Anagram

2 approaches, code in every language

Given two strings, decide whether the second is an anagram of the first. Two strings qualify as anagrams when they have the same length and every character occurs the same number of times in both.

Return true when the second string is a rearrangement of the first, and false otherwise.

Example 1

Input: s = "listen", t = "silent"

Output: true

Both strings use the letters e, i, l, n, s, t exactly once, so one is a rearrangement of the other.

Example 2

Input: s = "hello", t = "world"

Output: false

The letter counts differ (for instance 'l' appears twice in "hello" but once in "world"), so they are not anagrams.

Constraints

1 <= s.length <= 5 * 10^4
1 <= t.length <= 5 * 10^4
s and t consist of lowercase English letters

Frequency Counting

Count each character in the first string, decrement while scanning the second, and confirm nothing goes negative.

Loading animation…

Intuition

Anagrams have identical character multisets, so if you add one for each letter of the first string and subtract one for each letter of the second, every tally must cancel out to zero. A quick length check rejects mismatched sizes early. If any count dips below zero during the subtraction pass, the second string has a surplus of some letter and cannot be an anagram.

Algorithm walkthrough

1If the two strings differ in length, immediately return false.
2Increment a count for every character in the first string.
3Walk the second string and decrement the corresponding count.
4If any count becomes negative, return false.
5If the scan finishes without a negative count, return true.

Implementation

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        counts = {}
        for ch in s:
            counts[ch] = counts.get(ch, 0) + 1
        for ch in t:
            if counts.get(ch, 0) == 0:
                return False
            counts[ch] -= 1
        return True

Time

O(n)

Space

O(1)

A single count table over the 26-letter alphabet keeps extra space constant.

Sort And Compare

Sort both strings and check whether the sorted forms are identical.

Loading animation…

Intuition

Sorting places letters in a canonical order, so two anagrams collapse to the exact same sorted sequence. This trades the linear counting pass for an O(n log n) sort, but it is compact and easy to reason about: if the sorted characters match position by position, the strings are anagrams.

Algorithm walkthrough

1Return false right away if the lengths are unequal.
2Copy each string into a mutable character sequence.
3Sort both sequences alphabetically.
4Compare the two sorted sequences element by element.
5Return true only if they are exactly equal.

Implementation

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

Time

O(n log n)

Space

O(n)

Dominated by sorting both strings; extra space holds the mutable sorted copies.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Matching Letter Tally is our own problem on the technique behind Valid Anagram: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free