Group Anagrams: dùng chuỗi đã sort làm bucket key

Valid Anagram là câu hỏi có/không. Group Anagrams là cùng ý tưởng đó được biến thành bài toán phân bucket: với mỗi chuỗi trong input, tính một key giống nhau cho tất cả các anagram của nó, rồi thả vào đúng bucket. Không có chuỗi nào được so sánh với chuỗi nào khác. Một map, một lượt duyệt.

Constraints đang nói gì với bạn

Input có tối đa 10,000 chuỗi, mỗi chuỗi tối đa 100 ký tự, tất cả đều là chữ thường tiếng Anh. Ba điều lập tức suy ra từ đây.

Thứ nhất, n = 10⁴ loại bỏ mọi thứ có độ phức tạp bậc hai. Nested scan — kiểm tra mỗi chuỗi mới với từng nhóm đã có — sẽ chạm 10⁸ thao tác trong trường hợp tệ nhất và vượt time limit. Bạn cần O(n) hoặc O(n · cái gì đó nhỏ).

Thứ hai, chuỗi ngắn (m ≤ 100) và alphabet bị giới hạn (26 ký tự). Cả hai điều này làm cho việc đếm ký tự rẻ. Sort 100 ký tự tốn 100 · log(100) ≈ 700 phép so sánh. Xây mảng tần số 26 phần tử tốn đúng 100 phép cộng.

Thứ ba, constraint chỉ có chữ thường nghĩa là bạn có thể dùng mảng số nguyên kích thước cố định làm key thay vì dictionary. Đây là nền tảng cho frequency-tuple approach được mô tả sau.

Brute force: O(n² · m log m)

Approach rõ ràng nhất: với mỗi chuỗi mới, duyệt qua tất cả các nhóm đã tạo. Nếu phần tử đầu tiên của bất kỳ nhóm nào là anagram của chuỗi hiện tại, thêm chuỗi đó vào nhóm. Nếu không có nhóm nào khớp, tạo nhóm mới.

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        result: list[list[str]] = []
        for s in strs:
            placed = False
            for group in result:
                if sorted(s) == sorted(group[0]):
                    group.append(s)
                    placed = True
                    break
            if not placed:
                result.append([s])
        return result

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var result = new List<IList<string>>();
        foreach (string s in strs) {
            bool placed = false;
            char[] sChars = s.ToCharArray();
            Array.Sort(sChars);
            foreach (var group in result) {
                char[] g0Chars = group[0].ToCharArray();
                Array.Sort(g0Chars);
                if (new string(sChars) == new string(g0Chars)) {
                    group.Add(s);
                    placed = true;
                    break;
                }
            }
            if (!placed)
                result.Add(new List<string> { s });
        }
        return result;
    }
}

Duyệt qua ["eat","tea","tan","ate","nat","bat"] từng bước để thấy approach này vỡ ở đâu:

• "eat": chưa có nhóm nào. Tạo nhóm mới: [["eat"]].
• "tea": kiểm tra đại diện nhóm 0 là "eat". Sort cả hai -> "aet" == "aet". Thêm vào nhóm 0: [["eat","tea"]].
• "tan": kiểm tra nhóm 0 đại diện "eat" -> "ant" != "aet". Không khớp. Nhóm mới: [["eat","tea"],["tan"]].
• "ate": kiểm tra nhóm 0 -> "aet" == "aet". Khớp: [["eat","tea","ate"],["tan"]].
• "nat": kiểm tra nhóm 0 -> "ant" != "aet". Kiểm tra nhóm 1 -> "ant" == "ant". Khớp: [["eat","tea","ate"],["tan","nat"]].
• "bat": kiểm tra nhóm 0 -> miss. Kiểm tra nhóm 1 -> miss. Nhóm mới: [["eat","tea","ate"],["tan","nat"],["bat"]].

Kết quả đúng. Nhưng trong trường hợp tệ nhất — giả sử 10,000 chuỗi không có anagram nào — bạn kiểm tra chuỗi thứ k với k-1 nhóm. Tổng cộng 0 + 1 + 2 + ... + (n-1) = O(n²) lần kiểm tra nhóm, mỗi lần tốn O(m log m) để sort. Tại n = 10⁴ và m = 100, đó là 10¹⁰ thao tác ký tự. Quá chậm.

Sorted-key approach: O(n · m log m)

Hash map loại bỏ hoàn toàn việc scan. Thay vì kiểm tra từng nhóm đã có, bạn tính một key cho chuỗi hiện tại và để map định tuyến đến đúng bucket trong O(m) thời gian.

Insight cốt lõi: hai chuỗi là anagram khi, và chỉ khi, chúng sort ra cùng một chuỗi. "eat", "tea", và "ate" đều sort thành "aet". Dùng chuỗi đã sort đó làm bucket key.

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        buckets: dict[str, list[str]] = {}
        for s in strs:
            key = "".join(sorted(s))
            buckets.setdefault(key, []).append(s)
        return list(buckets.values())

Cùng ví dụ trên, trace từng bước qua map:

"eat" -> sort -> "aet" -> buckets = {"aet": ["eat"]}
"tea" -> sort -> "aet" -> buckets = {"aet": ["eat","tea"]}
"tan" -> sort -> "ant" -> buckets = {"aet": ["eat","tea"], "ant": ["tan"]}
"ate" -> sort -> "aet" -> buckets = {"aet": ["eat","tea","ate"], "ant": ["tan"]}
"nat" -> sort -> "ant" -> buckets = {"aet": ["eat","tea","ate"], "ant": ["tan","nat"]}
"bat" -> sort -> "abt" -> buckets = {"aet": [...], "ant": [...], "abt": ["bat"]}

Một lookup mỗi chuỗi. Không có vòng lặp qua các nhóm đã có.

Luồng xử lý cho mỗi chuỗi trông như thế này:

setdefault là Python idiom gọn nhất ở đây. Nó trả về list hiện có nếu key đã có, chèn list rỗng và trả về nếu chưa có — một lần gọi thay vì cái bước if key in dict quen thuộc. defaultdict(list) cũng tương đương:

from collections import defaultdict
 
class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        buckets: defaultdict[str, list[str]] = defaultdict(list)
        for s in strs:
            buckets["".join(sorted(s))].append(s)
        return list(buckets.values())

Tôi dùng defaultdict khi xây cấu trúc nhóm trong production code. setdefault trong vòng lặp chặt có overhead nhỏ vì nó tạo giá trị mặc định ngay cả khi key đã có; defaultdict thì không. Sự khác biệt không đáng kể ở 10⁴ chuỗi, nhưng đáng biết.

Tương đương trong C#:

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var buckets = new Dictionary<string, List<string>>();
        foreach (string s in strs) {
            char[] chars = s.ToCharArray();
            Array.Sort(chars);
            string key = new string(chars);
            if (!buckets.TryGetValue(key, out var group)) {
                group = new List<string>();
                buckets[key] = group;
            }
            group.Add(s);
        }
        return buckets.Values.Cast<IList<string>>().ToList();
    }
}

Cast<IList<string>>().ToList() ở dòng cuối là điều khó chịu nhỏ: Dictionary<string, List<string>>.Values cho bạn ICollection<List<string>>, nhưng kiểu trả về là IList<IList<string>>. Cast là bắt buộc vì C# không suy ra covariance cho generic collection. Nó cấp phát một list mới chứa các interface reference — O(k) với k là số nhóm phân biệt — hoàn toàn ổn.

Frequency-tuple key: O(n · m)

Thay vì sort, xây dựng cùng mảng tần số 26 phần tử từ Valid Anagram và dùng nó làm key:

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        buckets: dict[tuple[int, ...], list[str]] = {}
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            key = tuple(count)
            buckets.setdefault(key, []).append(s)
        return list(buckets.values())

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var buckets = new Dictionary<string, List<string>>();
        foreach (string s in strs) {
            int[] count = new int[26];
            foreach (char c in s) {
                count[c - 'a']++;
            }
            string key = string.Join(",", count);
            if (!buckets.TryGetValue(key, out var group)) {
                group = new List<string>();
                buckets[key] = group;
            }
            group.Add(s);
        }
        return buckets.Values.Cast<IList<string>>().ToList();
    }
}

O(n · m) — tuyến tính theo tổng số ký tự, không sort. Về lý thuyết, tốt hơn sorted-key với chuỗi dài.

Trong thực tế, hằng số quan trọng. Một tuple gồm 26 số nguyên chiếm nhiều bộ nhớ hơn một chuỗi ngắn đã sort ("aet" là 3 byte; tuple tương đương của nó là 26 số nguyên). Hash một tuple 26 phần tử cũng tốn công hơn hash một chuỗi 3 ký tự, dù cả hai đều là O(m) về mặt asymptotic. Trên test case của LeetCode — phần lớn chuỗi ngắn — version sorted-key thường chạy nhanh hơn vì các key rất nhỏ.

Tôi sẽ dùng frequency-tuple khi chuỗi dài và alphabet ký tự bị giới hạn. Với bài này, cả hai đều đúng và sự khác biệt chỉ là artifact của test suite. Biết cả hai; mặc định chọn cái dễ đọc hơn.

So sánh các approach

Space đều là O(n · m) cho cả ba — bạn phải lưu tất cả các chuỗi ở đâu đó.

Edge case, từng trường hợp

Chuỗi rỗng [""]: Chuỗi rỗng sort thành "", là một map key hợp lệ. Nó có bucket riêng và output là [[""]]. Không cần xử lý đặc biệt trong cả hai approach.

Tất cả chuỗi giống nhau ["abc","abc","abc"]: Cả ba tạo key "abc" (đã sort sẵn) và rơi vào một bucket. Output là [["abc","abc","abc"]]. Map chỉ có đúng một entry.

Không có anagram nào ["a","b","c"]: Mỗi chuỗi là key của riêng nó. Map lớn lên đến ba entry và output là [["a"],["b"],["c"]]. Cả hai approach không gặp vấn đề gì — chỉ tạo ra nhiều single-element bucket.

Một chuỗi duy nhất ["a"]: Một lần lặp, một bucket, output [["a"]]. Brute force cũng xử lý đúng mà không cần vào vòng lặp trong.

Tất cả chuỗi là anagram ["abc","bca","cab"]: Mọi chuỗi đều tạo key "abc". Một bucket, một nhóm output. Đây là best case cho map: output kích thước hằng số bất kể input dài.

Nhận diện pattern

Group Anagrams nằm ở giao điểm của hai tín hiệu quen thuộc. Thứ nhất: "nhóm các phần tử có cùng tính chất" hầu như luôn có nghĩa là "suy ra canonical key và dùng hash map." Key là bất cứ thứ gì bạn có thể tính từ một phần tử đơn mà giống nhau cho tất cả phần tử trong cùng nhóm.

Thứ hai: khi bài toán nói "anagram," hãy nghĩ đến sort-to-canonical hoặc character counting. Cả hai đều biến phép so sánh phụ thuộc thứ tự thành signature độc lập thứ tự.

Keywords nên trigger pattern này: "group," "cluster," "categorize," "same characters," "rearrange," "permutation of." Nếu output là list of lists mà mỗi inner list chứa các item "giống nhau," bạn hầu như chắc chắn đang nhìn vào bài canonical-key bucketing.

Bài học rộng hơn: khi bạn thấy mình viết "với mỗi phần tử, scan tất cả các phần tử đã thấy để kiểm tra sự giống nhau," hãy dừng lại. Nested scan đó hầu như luôn có thể thay bằng map từ một derived key đến một nhóm.

Vị trí trong series

Contains Duplicate: seen set, chỉ kiểm tra membership. Valid Anagram: frequency map, bằng nhau về số lần đếm. Group Anagrams: sorted key làm nhãn bucket, không so sánh phần tử với phần tử nào cả. Mỗi bước giảm số lần so sánh mỗi phần tử — từ O(n) scan xuống O(1) map lookup — bằng cách chọn key thông minh hơn.

Bước mở rộng tự nhiên tiếp theo là Top K Frequent Elements, nơi key không phải là bản thân phần tử hay dạng đã sort của nó mà là tần số xuất hiện. Cùng phản xạ bucketing, key dẫn xuất khác.

Related problems

• 242. Valid Anagram — bài tiền nhiệm trực tiếp. Kiểm tra một cặp thay vì group-by. Hiểu bài này trước làm cho việc suy ra key ở đây trở nên hiển nhiên.
• 438. Find All Anagrams in a String — frequency-array approach kết hợp sliding window. Cùng mảng đếm 26 phần tử, cập nhật liên tục khi window trượt.
• 567. Permutation in String — giống 438 nhưng trả về boolean. Window management đơn giản hơn một chút.