Valid Anagram

easy
Arrays & HashingStringHash TableSorting

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once.

Examples

Example 1

  • Input: s = "anagram", t = "nagaram"
  • Output: true
  • Explanation: Both strings contain the same characters with the same frequencies.

Example 2

  • Input: s = "rat", t = "car"
  • Output: false

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Sorting

Intuition

If two strings are anagrams, sorting them will produce the same string. We can sort both strings and compare them directly. If the sorted versions are equal, the strings are anagrams. This is simple to implement but sorting dominates the time complexity.

Algorithm

  1. If the lengths of s and t differ, return false immediately.
  2. Sort both strings.
  3. Compare the sorted strings. If they are equal, return true; otherwise return false.
TimeO(n log n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};
Java 21
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Arrays.sort(sArr);
        Arrays.sort(tArr);
        return Arrays.equals(sArr, tArr);
    }
}
Python 3.12
def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)
Go 1.26
import "sort"

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    sBytes := []byte(s)
    tBytes := []byte(t)
    sort.Slice(sBytes, func(i, j int) bool { return sBytes[i] < sBytes[j] })
    sort.Slice(tBytes, func(i, j int) bool { return tBytes[i] < tBytes[j] })
    return string(sBytes) == string(tBytes)
}
Approach 2

Character Frequency Count

Intuition

Since anagrams have identical character frequencies, we can count the occurrence of each character in both strings and compare. Using an array of 26 integers (for lowercase English letters), increment the count for each character in s and decrement for each character in t. If all counts are zero at the end, the strings are anagrams. This runs in linear time.

Algorithm

  1. If the lengths of s and t differ, return false.
  2. Create an integer array of size 26 initialized to zero.
  3. Iterate through both strings simultaneously: increment the count for s[i] and decrement the count for t[i].
  4. Check if all 26 counts are zero. If so, return true; otherwise return false.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;

        int count[26] = {0};
        for (int i = 0; i < s.length(); i++) {
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }

        for (int c : count) {
            if (c != 0) return false;
        }
        return true;
    }
};
Java 21
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 3.12
def isAnagram(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

    return all(c == 0 for c in count)
Go 1.26
func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    var count [26]int
    for i := 0; i < len(s); i++ {
        count[s[i]-'a']++
        count[t[i]-'a']--
    }

    for _, c := range count {
        if c != 0 {
            return false
        }
    }
    return true
}

Frequently asked questions

What is the optimal time complexity of Valid Anagram?

The most efficient approach in this guide ("Character Frequency Count") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Valid Anagram use?

Valid Anagram is a easy-level Arrays & Hashing problem involving String, Hash Table, Sorting. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Valid Anagram be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Group Anagrams

Original problem: leetcode.com

Loading editor...
Input
s=
"anagram"
t=
"nagaram"
Expected Output
true