Valid Anagram: đếm ký tự thay vì so sánh vị trí

Hai chuỗi là anagram của nhau khi chúng chứa cùng các ký tự với cùng số lần xuất hiện — thứ tự không quan trọng. "anagram" và "nagaram" là anagram: cả hai đều có ba a, một n, một g, một r, một m. "rat" và "car" thì không: r, a, t so với c, a, r.

Câu hỏi chỉ là: làm thế nào kiểm tra tần số ký tự bằng nhau một cách hiệu quả?

Trước mọi logic, kiểm tra độ dài là miễn phí và có tính quyết định. Nếu len(s) != len(t), xong ngay — độ dài khác nhau không thể cho ra tần số ký tự bằng nhau. Một early return đó loại bỏ cả một nhóm input trước khi chạm vào ký tự nào.

Constraint thực sự buộc ta làm gì

Đề nói s và t chỉ chứa chữ cái thường tiếng Anh, và 1 <= s.length, t.length <= 5 * 10^4.

Đọc "chỉ chứa chữ cái thường tiếng Anh" theo nghĩa đen: tập ký tự chỉ có đúng hai mươi sáu giá trị. Đây là giới hạn cố định, không phải biến. Nghĩa là một mảng integer 26 phần tử là bản đồ ký tự hoàn chỉnh — không cần cấp phát động, không có hash collision, toàn bộ bảng chữ cái vừa trong một cache line. Constraint này không phải ngẫu nhiên. Nó đang chỉ ra đúng cấu trúc dữ liệu cần dùng.

Đọc n <= 5 * 10^4 như một điểm qua lỏng cho O(n log n) — năm mươi nghìn phần tử sort xong chưa đến một mili giây — nhưng nó không loại trừ O(n). Bảng chữ cái cố định làm O(n) khả thi, và O(n) tốt hơn tuyệt đối, nên không có lý do gì dừng lại ở sorting.

Sorting: đúng nhưng tốn hơn cần thiết

Mental model đơn giản nhất: sort cả hai chuỗi, so sánh. Các anagram luôn sort ra cùng một chuỗi.

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

Trong Python đây là one-liner thực sự. Nó xử lý length mismatch ngầm — nếu độ dài khác nhau thì kết quả sort khác nhau, phép so sánh vẫn trả về False mà không cần check tường minh.

Trong C# cần thêm vài dòng vì phải materialize các sorted array:

public class Solution {
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length) return false;
        char[] sArr = s.ToCharArray();
        char[] tArr = t.ToCharArray();
        Array.Sort(sArr);
        Array.Sort(tArr);
        return new string(sArr) == new string(tArr);
    }
}

Cái giá là O(n log n) thời gian và O(n) bộ nhớ. Bạn đang tính một thứ tự ký tự đầy đủ trong khi chỉ cần kiểm tra tần số bằng nhau. Sorting tạo ra thông tin — một chuỗi có thứ tự toàn cục — rồi bạn loại bỏ ngay sau khi so sánh. Đó là phần dư thừa. Với n = 5 * 10^4 trong bối cảnh LeetCode thì không thành vấn đề, nhưng trong pipeline xử lý hàng triệu chuỗi thì có.

Frequency array: O(n) thời gian, O(1) bộ nhớ

Constraint đã nói tập ký tự có kích thước 26. Một mảng integer 26 phần tử được đánh index bằng char - 'a' là bảng tần số hoàn chỉnh. Cách làm: tăng cho mọi ký tự trong s, giảm cho mọi ký tự trong t. Nếu hai chuỗi là anagram, mọi lần tăng từ s đều bị triệt tiêu bởi một lần giảm tương ứng từ t, và mảng kết thúc ở trạng thái tất cả bằng 0.

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)

zip(s, t) tiêu thụ cả hai chuỗi trong một lượt duyệt. ord(a) - ord('a') ánh xạ 'a' sang 0, 'b' sang 1, ... 'z' sang 25. all(c == 0 ...) cuối cùng quét đúng 26 phần tử — công việc hằng số bất kể độ dài input.

Trace s = "anagram", t = "nagaram" từng bước. Bắt đầu: count = [0] * 26.

Mọi slot đều trở về 0 vì mọi ký tự mà s đóng góp, t cũng có. Các giá trị -1 xuất hiện giữa chừng — count[13] = -1 sau cặp đầu tiên, count[6] = -1 sau cặp thứ ba — biểu thị ký tự đã thấy trong t trước khi ký tự tương ứng trong s xuất hiện. Không sao. Điều duy nhất quan trọng là trạng thái cuối cùng.

Trong C#, phép trừ ký tự hoạt động trực tiếp vì phép tính trên char được định nghĩa:

public class Solution {
    public bool 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[i] - 'a']++;
            count[t[i] - 'a']--;
        }
        foreach (int c in count) {
            if (c != 0) return false;
        }
        return true;
    }
}

s[i] - 'a' ánh xạ 'a' -> 0, 'b' -> 1, ... 'z' -> 25. Cùng phép tính với ord() - ord('a') trong Python. Vòng foreach return sớm ngay khi gặp phần tử khác 0 — trong trường hợp trả về False, điều này tránh quét các slot còn lại.

Shortcut Counter trong Python

from collections import Counter
 
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

Hai dòng. Counter xây frequency dictionary cho mỗi chuỗi; == so sánh chúng theo nội dung. Đây là Python idiomatic và tự động xử lý Unicode vì dictionary không có giới hạn phạm vi key. O(n) thời gian, O(k) bộ nhớ với k là số ký tự phân biệt — nhiều nhất 26 với chữ thường tiếng Anh, nên thực chất bằng với mảng.

Tôi sẽ dùng Counter trong production Python. Trong phỏng vấn tôi viết version mảng tường minh trước rồi đề cập Counter như shortcut idiomatic — vì cho thấy bạn hiểu cơ chế đếm tần số có giá trị hơn là chỉ biết một class stdlib tồn tại.

So sánh tất cả các approach

Follow-up Unicode

Đề hỏi thêm: nếu input có thể chứa ký tự Unicode thì sao?

Mảng 26 phần tử không còn dùng được — bạn không thể giới hạn giá trị ký tự vào 0-25. Cách frequency dictionary tổng quát hoá trực tiếp mà không thay đổi cấu trúc:

from collections import Counter
 
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

Cùng code. Counter chấp nhận bất kỳ key hashable nào, nên mọi ký tự Unicode đều trở thành dictionary key. Bộ nhớ giờ là O(k) với k là số ký tự phân biệt trong input thực tế — không bị chặn về lý thuyết, bị chặn trong thực tế bởi những gì chuỗi thực sự chứa.

Trong C#, cách Dictionary-based là cùng ý tưởng với mảng, chỉ thay index cố định bằng hash map:

public class Solution {
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length) return false;
        var count = new Dictionary<char, int>();
        foreach (char c in s)
            count[c] = count.GetValueOrDefault(c, 0) + 1;
        foreach (char c in t) {
            if (!count.ContainsKey(c)) return false;
            count[c]--;
            if (count[c] == 0) count.Remove(c);
        }
        return count.Count == 0;
    }
}

Việc Remove khi count về 0 giữ cho phép kiểm tra .Count == 0 cuối cùng gọn gàng. Không làm vậy thì phải kiểm tra xem tất cả giá trị còn lại có bằng 0 không — đúng về logic nhưng rối hơn. Xóa key khi count về 0 có nghĩa là dictionary không rỗng ở cuối mang ý nghĩa ngay lập tức: một ký tự nào đó xuất hiện số lần không bằng nhau.

Các edge case đáng biết

Độ dài khác nhau — early return xử lý trước khi xử lý bất kỳ ký tự nào. Tốn O(1).

Hai chuỗi giống hệt nhau — s = t = "abc": mọi ký tự trong s tăng count, và cùng ký tự đó ở cùng vị trí trong t giảm ngay lập tức. Mọi slot về 0. Trả về True. Đúng: một chuỗi hiển nhiên là anagram của chính nó.

Một ký tự — "a" vs "a": một lần tăng, một lần giảm, count[0] = 0, trả về True. "a" vs "b": count[0] = 1, count[1] = -1, không phải tất cả bằng 0, trả về False. Cả hai đều đúng.

Tất cả cùng một ký tự — "aaaa" vs "aaaa": count[0] dao động +1, -1, +1, -1, +1, -1, +1, -1 qua bốn cặp zip, kết thúc ở 0. Ổn.

Ký tự xuất hiện ở một chuỗi nhưng không ở chuỗi kia — "abc" vs "abd": sau toàn bộ lượt duyệt, count[2] = 1 (thừa c từ s, chưa bao giờ bị triệt tiêu), count[3] = -1 (bị giảm bởi d từ t, chưa bao giờ được tăng). Không phải tất cả bằng 0, trả về False. Giá trị âm ở đây có ý nghĩa — nó nói t có ký tự mà s không có.

Pattern và mental model

Pattern cốt lõi là frequency counting: khi bạn cần xác nhận hai collection chứa cùng phần tử với cùng số lần, duy trì một bảng hiệu và kiểm tra nó kết thúc ở 0. Đây là nâng cấp từ set membership pattern đã dùng trong Contains Duplicate.

Contains Duplicate hỏi: tôi đã thấy giá trị này chưa? Một set trả lời — một bit mỗi giá trị.

Valid Anagram hỏi: tôi đã thấy giá trị này cùng số lần trong cả hai dãy chưa? Một count map trả lời — một integer mỗi giá trị.

Chiều thêm đó — đếm thay vì sự hiện diện — xuất hiện trong nhiều bài ngay sau bài này. Group Anagrams dùng cùng thông tin tần số nhưng như dictionary key để gom chuỗi vào nhóm. Find All Anagrams in a String áp dụng nó bên trong sliding window trên chuỗi dài hơn, duy trì frequency array tăng dần khi window dịch chuyển.

Vị trí trong series

Two Sum dùng hash map value -> index. Contains Duplicate dùng set để kiểm tra membership. Valid Anagram giới thiệu frequency map: bạn không còn quan tâm xem đã thấy giá trị chưa, mà quan tâm đã thấy bao nhiêu lần.

Sự mở rộng đó chính xác là thứ Group Anagrams cần ở bài tiếp theo. Thay vì kiểm tra hai chuỗi có tần số bằng nhau không, bạn dùng chuỗi đã sort hoặc count tuple làm grouping key — cùng logic tần số nền tảng, giờ áp dụng như bucket identifier thay vì phép kiểm tra boolean.

Ba bài liên quan đáng giải sau bài này:

• 49. Group Anagrams — frequency tuple hoặc sorted-string key để gom anagram vào nhóm. Frequency counting là giống hệt; thách thức mới là dùng nó làm dictionary key trên nhiều chuỗi.
• 438. Find All Anagrams in a String — sliding window duy trì frequency array tăng dần. Window tiến một ký tự mỗi bước: tăng ký tự mới vào, giảm ký tự ra. So sánh array của window với array của pattern chính xác là phép kiểm tra Valid Anagram, áp dụng ở mọi vị trí.
• 567. Permutation in String — cấu trúc giống hệt 438 nhưng hỏi có permutation nào không thay vì liệt kê vị trí. Cùng sliding window, cùng frequency matching.