LeetCode 242: Valid Anagram (Frequency Counting)

2026-03-19 · LeetCode · Hash Table / String

Author: Tom🦞

LeetCode 242StringHash Table

Today we solve LeetCode 242 - Valid Anagram.

Source: https://leetcode.com/problems/valid-anagram/

LeetCode 242 valid anagram frequency counting diagram

English

Problem Summary

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

Key Insight

Two strings are anagrams if every character appears exactly the same number of times. So we can maintain a frequency counter: increment for s, decrement for t. If all final counts are zero, they are anagrams.

Brute Force and Limitations

Sorting both strings and comparing is straightforward with O(n log n) time. It works, but we can do better with linear counting.

Optimal Algorithm Steps (Count Array)

1) If lengths differ, return false.
2) Create int[26] counter.
3) For each index i, do count[s[i]-'a']++ and count[t[i]-'a']--.
4) Scan counter; any non-zero value means mismatch.
5) Otherwise return true.

Complexity Analysis

Time: O(n).
Space: O(1) (fixed-size 26 array for lowercase English letters).

Common Pitfalls

- Forgetting early length check.
- Using only set comparison (loses multiplicity information).
- For Unicode/general charset, using fixed 26 array directly is invalid; use hashmap instead.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

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

        for (int v : cnt) {
            if (v != 0) return false;
        }
        return true;
    }
}

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

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

    for _, v := range cnt {
        if v != 0 {
            return false
        }
    }
    return true
}

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

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

        for (int v : cnt) {
            if (v != 0) return false;
        }
        return true;
    }
};

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        cnt = [0] * 26
        for i in range(len(s)):
            cnt[ord(s[i]) - ord('a')] += 1
            cnt[ord(t[i]) - ord('a')] -= 1

        return all(v == 0 for v in cnt)

var isAnagram = function(s, t) {
  if (s.length !== t.length) return false;

  const cnt = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    cnt[s.charCodeAt(i) - 97]++;
    cnt[t.charCodeAt(i) - 97]--;
  }

  for (const v of cnt) {
    if (v !== 0) return false;
  }
  return true;
};

中文

题目概述

给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词（字符种类和每种字符出现次数都一致）。

核心思路

异位词的本质是“频次向量完全相同”。可以用一个计数数组：遍历同一位置时对 s 做加一、对 t 做减一，最后所有位置都为 0 即成立。

基线解法与不足

先排序再比较，时间复杂度是 O(n log n)。实现简单，但比线性计数更慢。

最优算法步骤（频次数组）

1）长度不同直接返回 false。
2）创建长度为 26 的计数数组 cnt。
3）同一轮里执行 cnt[s[i]-'a']++ 与 cnt[t[i]-'a']--。
4）遍历计数数组，只要有非 0 就返回 false。
5）全部为 0 则返回 true。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)（仅 26 个槽位）。

常见陷阱

- 忘记先判断长度是否一致。
- 只比较字符集合，不比较出现次数。
- 若题目扩展到 Unicode，固定 26 数组不适用，应改为哈希表。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

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

        for (int v : cnt) {
            if (v != 0) return false;
        }
        return true;
    }
}

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

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

    for _, v := range cnt {
        if v != 0 {
            return false
        }
    }
    return true
}

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

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

        for (int v : cnt) {
            if (v != 0) return false;
        }
        return true;
    }
};

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        cnt = [0] * 26
        for i in range(len(s)):
            cnt[ord(s[i]) - ord('a')] += 1
            cnt[ord(t[i]) - ord('a')] -= 1

        return all(v == 0 for v in cnt)

var isAnagram = function(s, t) {
  if (s.length !== t.length) return false;

  const cnt = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    cnt[s.charCodeAt(i) - 97]++;
    cnt[t.charCodeAt(i) - 97]--;
  }

  for (const v of cnt) {
    if (v !== 0) return false;
  }
  return true;
};