Valid Anagram

Easy Problem 3 of 151 Java and Python

Practice on LeetCode

Problem

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

An anagram uses exactly the same letters as the original, each the same number of times, in any order.

Example 1

Input: s = "anagram", t = "nagaram"
Output: true

Example 2

Input: s = "rat", t = "car"
Output: false
Why: "rat" has a t, "car" has a c.

Constraints

1 ≤ s.length, t.length ≤ 5 × 10⁴
s and t contain only lowercase English letters.

Explanation

Two strings are anagrams exactly when they have the same letter counts. Sorting both strings makes equal counts look identical; counting letters checks it directly.

With only 26 lowercase letters, a fixed array of 26 counters is all the memory you need.

Approach 1 · Naive

Sort both strings

Time O(n log n)
Space O(n)

Sorted anagrams are the same string, so sort the characters of both and compare.

If the lengths differ, return false.
Sort the characters of s and of t.
Return whether the sorted versions are equal.

Java

import java.util.*;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a, b);
    }
}

Python

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

Approach 2 · Optimal

Count letters

Time O(n)
Space O(1) (26 counters)

Add one for each letter of s and subtract one for each letter of t. They are anagrams only if every counter ends at zero.

If the lengths differ, return false.
Make an array of 26 zeros.
For each index, increment the count of s[i] and decrement the count of t[i].
Return true if all counts are zero.

Java

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int c : count) {
            if (c != 0) {
                return false;
            }
        }
        return true;
    }
}

Python

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        count = [0] * 26
        for a, b in zip(s, t):
            count[ord(a) - ord('a')] += 1
            count[ord(b) - ord('a')] -= 1
        return all(c == 0 for c in count)

Complexity compared

Approach	Time	Space
Naive Sort both strings	O(n log n)	O(n)
Optimal Count letters	O(n)	O(1) (26 counters)

Key takeaways

A small fixed alphabet means a counting array beats a hash map.
Follow-up: for Unicode input, use a hash map of character counts instead of 26 slots.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem