242. Valid Anagram

← All Problems
easy Strings & Sliding Window
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.

Example

s = "anagram", t = "nagaram"

Output: true

Both strings contain exactly the same letters with the same frequencies: three as, one n, one g, one r, and one m. Since t is just a rearrangement of s, it is a valid anagram.

Two strings are anagrams if and only if they have the exact same character frequencies. Count the frequency of each character in both strings using an array of size 26 (for lowercase English letters), then check that every count matches.

Why this works

Two strings are anagrams if they use exactly the same letters the same number of times. By incrementing a counter for each character in s and decrementing for each character in t, you end up with all zeros only when the frequencies match perfectly.

Step by step

  1. Quick length check — if the strings have different lengths, they cannot be anagrams.
  2. Count simultaneously — walk both strings at once, incrementing for s and decrementing for t in a 26-slot array.
  3. Check for all zeros — if every slot is zero, the character frequencies match exactly, confirming an anagram.
Time: O(n) Space: O(1) 
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] count = new int[26];  // one slot per letter a-z
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;  // count up for s
            count[t.charAt(i) - 'a']--;  // count down for t
        }
        for (int c : count) {
            if (c != 0) return false;  // any non-zero means frequencies differ
        }
        return true;
    }
}

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }
        int count[26] = {0};  // one slot per letter a-z
        for (int i = 0; i < s.size(); i++) {
            count[s[i] - 'a']++;  // count up for s
            count[t[i] - 'a']--;  // count down for t
        }
        for (int c : count) {
            if (c != 0) return false;  // any non-zero means frequencies differ
        }
        return true;
    }
};

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    count = [0] * 26  # one slot per letter a-z
    for i in range(len(s)):
        count[ord(s[i]) - ord('a')] += 1  # count up for s
        count[ord(t[i]) - ord('a')] -= 1  # count down for t
    return all(c == 0 for c in count)      # all zeros means perfect match