3. Valid Anagram · DSA Practice

Given two lowercase strings s and t, return true if t is an anagram of s: it uses exactly the same letters, the same number of times.

Example 1

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

Output: true

Example 2

Input: s = "rat", t = "car"

Output: false

Constraints

0 ≤ s.length, t.length ≤ 5·10⁴
Lowercase English letters only

Hint 1

Two words are anagrams when their letter counts match.

StringCounting

Approach 1: Sort both

Sort the characters of both strings and compare.

⏱ Time O(n log n)💾 Space O(n)

Approach 2: Count letters ✅

One array of 26 counters: add for s, subtract for t; all counters must end at zero.

⏱ Time O(n)💾 Space O(1)

Reference solution for Count letters (time O(n), space O(1)). Each solution passes every test in all four languages.

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) - 97] += 1   # +1 for letters of s
            count[ord(b) - 97] -= 1   # -1 for letters of t
        return all(c == 0 for c in count)

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;
    }
}

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;
        int count[26] = {0};
        for (size_t i = 0; i < s.size(); i++) {
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }
        for (int c : count) if (c != 0) return false;
        return true;
    }
};

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++;
    count[t.charCodeAt(i) - 97]--;
  }
  return count.every(c => c === 0);
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Arrays, Hashing & Prefix Sums.