1.1 Vì sao Hashing là pattern quan trọng nhất?

Tuần 1 đã giới thiệu mantra "đổi space lấy time". Tuần 3 đào sâu cách áp dụng nó.

Ba câu hỏi bài toán mà hash giải quyết hoàn hảo

1. "X có tồn tại không?" → set + x in s O(1).
2. "X xuất hiện bao nhiêu lần?" → dict / Counter O(1) per query.
3. "Hai đối tượng có cùng đặc trưng không?" → so sánh hash key của chúng.

Nếu có, thì câu hỏi tiếp theo là: key của hash sẽ là gì? Đó là phần nghệ thuật.

1.2 Cơ chế bên trong — Vì sao O(1) trung bình?

Cấu trúc

Hash table = mảng B "bucket" + hàm băm h(key). Vị trí lưu key là h(key) mod B.

Truy cập trung bình O(1)

Nếu hàm băm phân phối đều và n / B nhỏ (load factor < 1), mỗi bucket chứa ~1 phần tử. Tìm/thêm/xoá là O(1) trung bình.

Worst case

Nếu nhiều key băm cùng bucket (collision), chuỗi tại bucket dài lên. Tệ nhất: mọi key cùng bucket → O(n) per operation.

Python dict dùng open addressing + random hash seed; thực tế gần như không bao giờ degrade.

1.3 Ba cấu trúc Python — Khi nào dùng cái nào?

Counter — bốn thao tác đáng nhớ

from collections import Counter
c = Counter("aabbbc")           # Counter({'b': 3, 'a': 2, 'c': 1})

c.most_common(2)                # [('b', 3), ('a', 2)]
c['x']                          # 0  — không tồn tại trả 0, không lỗi

c1 = Counter("abc"); c2 = Counter("aab")
c1 + c2                         # Counter({'a': 3, 'b': 2, 'c': 1})
c1 & c2                         # min(intersection): Counter({'a': 1, 'b': 1})

1.4 Thiết kế key — Cái gì có thể là key?

Python yêu cầu key của dict/set phải hashable: hỗ trợ __hash__ và bất biến.

Kỹ thuật "đóng gói" key

# Sai: list không hashable
seen = set()
seen.add([1, 2, 3])                  # TypeError

# Đúng: chuyển thành tuple
seen.add(tuple([1, 2, 3]))           # OK

# Hoặc frozenset nếu thứ tự không quan trọng
seen.add(frozenset([1, 2, 3]))       # OK

2.1 Pattern Frequency Counting

cnt = Counter(data)            # Pha 1: O(n) — đếm
result = process(cnt)          # Pha 2: O(n) hoặc O(k) — xử lý dựa trên tần suất

Tín hiệu nhận biết trong đề

• Đề nói "đếm số lần xuất hiện".
• So sánh hai chuỗi/mảng theo nội dung chứ không theo thứ tự (anagram).
• Tìm phần tử đầu tiên / duy nhất xuất hiện k lần.
• Top K phần tử thường xuyên nhất.
• Sắp xếp theo tần suất.

Đặc điểm chung: thứ tự ban đầu không quan trọng, chỉ quan trọng tần suất. Đó là dấu hiệu Frequency Counting.

2.2 Worked Example 1 — Group Anagrams

Đề (LeetCode #49): Cho mảng string strs. Nhóm các anagram cùng group.

Ví dụ: ["eat","tea","tan","ate","nat","bat"] → [["bat"],["nat","tan"],["ate","eat","tea"]].

Câu hỏi cốt lõi: Key của hash là gì?

Key phải có tính chất: hai string là anagram \(\iff\) có cùng key.

Approach 1 — Sorted string làm key

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))     # "tea" → "aet"
        groups[key].append(s)
    return list(groups.values())

Time O(n × k log k) với k = độ dài chuỗi (sort mỗi chuỗi).

2.3 Group Anagrams — Tối ưu Key Design

Approach 2 — Tuple đếm 26 ký tự làm key

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - ord('a')] += 1
        key = tuple(cnt)             # tuple hashable, list thì không
        groups[key].append(s)
    return list(groups.values())

Time O(n × k) — không cần sort.

So sánh hai approach

2.4 Worked Example 2 — Top K Frequent Elements

Đề (LeetCode #347): Mảng nums. Trả về k phần tử xuất hiện nhiều nhất.

Constraints: Phải đạt tốt hơn O(n log n).

Approach 1 — Sort theo tần suất

from collections import Counter
def topKFrequent(nums, k):
    cnt = Counter(nums)
    return [x for x, _ in cnt.most_common(k)]
# Time O(n log n), đạt nhưng chưa tốt nhất

Approach 2 — Min Heap kích thước k

import heapq
def topKFrequent(nums, k):
    cnt = Counter(nums)
    return heapq.nlargest(k, cnt.keys(), key=cnt.get)
# Time O(n log k) — tốt hơn khi k << n

Heap sẽ học chi tiết ở Tuần 9.

2.5 Top K Frequent — Bucket Sort O(n)

Approach 3 — Bucket Sort theo tần suất

Quan sát: tần suất tối đa của một phần tử là n. Tạo n+1 bucket, bucket[f] chứa các phần tử có tần suất f. Duyệt ngược từ bucket lớn nhất.

def topKFrequent(nums, k):
    cnt = Counter(nums)
    n = len(nums)
    buckets = [[] for _ in range(n + 1)]
    for x, f in cnt.items():
        buckets[f].append(x)
    result = []
    for f in range(n, 0, -1):
        for x in buckets[f]:
            result.append(x)
            if len(result) == k:
                return result
    return result

Time O(n), Space O(n).

2.6 Worked Example 3 — First Unique Character

Đề (LeetCode #387): Cho string s. Trả về index của ký tự đầu tiên xuất hiện đúng một lần. Nếu không có, trả về -1.

Pattern hai pass

def firstUniqChar(s):
    cnt = Counter(s)              # Pass 1: đếm — O(n)
    for i, ch in enumerate(s):    # Pass 2: tìm theo thứ tự — O(n)
        if cnt[ch] == 1:
            return i
    return -1

Time O(n), Space O(k) với k = số ký tự khác nhau (≤ 26 cho chữ thường).

Biến thể: First Unique Character in a Stream phải dùng cấu trúc dữ liệu khác (queue + count).

2.7 Worked Example 4 — Find Common Characters

Đề (LeetCode #1002): Cho mảng các string words. Trả về các ký tự xuất hiện trong mọi string (kể cả trùng lặp).

Ví dụ: ["bella","label","roller"] → ["e","l","l"] (vì 'l' xuất hiện ≥ 2 trong cả 3 string, 'e' xuất hiện ≥ 1).

Pattern: giao multiset bằng Counter

from collections import Counter
from functools import reduce

def commonChars(words):
    common = reduce(lambda a, b: a & b, map(Counter, words))
    return list(common.elements())

Phân tích

• Counter(s) & Counter(t) = giao multiset — lấy min(count_s, count_t) cho mỗi ký tự.
• reduce áp dụng phép giao lần lượt qua các Counter.
• elements() "duỗi" Counter ra: Counter({'l':2,'e':1}) → ['l','l','e'].

Time O(n × k) với n = số string, k = độ dài trung bình.

Knowledge Check — Frequency Counting

3.1 Pattern Lookup

seen = {}                       # value → thông tin (index, count, time...)
for i, x in enumerate(arr):
    if <điều kiện ghép với cái đã thấy>:
        # tìm trong seen O(1)
        return ...
    seen[x] = i                 # ghi nhận đã thấy

Tín hiệu

• "Tìm cặp", "tìm bộ" thoả điều kiện cộng/hiệu/tích.
• "Trùng lặp trong khoảng cách k".
• "Mapping 1-1" giữa hai chuỗi.
• Bài có thể giải brute force O(n²) bằng cách duyệt cặp (i, j) — đây là dấu hiệu mạnh để thử chuyển sang lookup.

3.2 Worked Example 5 — Contains Duplicate II

Đề (LeetCode #219): Mảng nums, số k. Trả True nếu tồn tại i, j sao cho nums[i] == nums[j] và |i - j| ≤ k.

Brute force

# O(n × k)
for i in range(len(nums)):
    for j in range(i+1, min(i+k+1, len(nums))):
        if nums[i] == nums[j]: return True
return False

Pattern Lookup

def containsNearbyDuplicate(nums, k):
    seen = {}                          # value → last index
    for i, x in enumerate(nums):
        if x in seen and i - seen[x] <= k:
            return True
        seen[x] = i                    # cập nhật index mới nhất
    return False

Time O(n), Space O(n).

3.3 Contains Duplicate II — Trace tay

nums = [1, 2, 3, 1, 2, 3], k = 2. Kỳ vọng: False (mọi cặp trùng đều cách xa hơn 2).

Trả về False.

3.4 Worked Example 6 — Isomorphic Strings

Đề (LeetCode #205): Hai string s, t là isomorphic nếu có thể thay thế ký tự trong s để được t, mỗi ký tự ánh xạ duy nhất sang một ký tự khác, và khác ký tự nguồn ánh xạ tới khác ký tự đích.

Ví dụ: "egg" ↔ "add" → True (e→a, g→d). "foo" ↔ "bar" → False (o→a và o→r mâu thuẫn).

Pattern: hai map kiểm tra song ánh (bijection)

def isIsomorphic(s, t):
    if len(s) != len(t): return False
    s2t, t2s = {}, {}
    for a, b in zip(s, t):
        if a in s2t and s2t[a] != b: return False
        if b in t2s and t2s[b] != a: return False
        s2t[a] = b
        t2s[b] = a
    return True

Time O(n), Space O(k) với k = số ký tự khác nhau.

3.5 Isomorphic — Vì sao cần HAI map?

Nhiều sinh viên chỉ dùng 1 map (s → t) và sai trên test "ab" ↔ "aa".

Trace với 1 map (sai)

s = "ab", t = "aa"
i=0: 'a' không trong map → map['a'] = 'a'.   map = {'a':'a'}
i=1: 'b' không trong map → map['b'] = 'a'.   map = {'a':'a', 'b':'a'}
Trả True ✗ — nhưng đáp án thực sự là False.

Lỗi: cả 'a' và 'b' đều ánh xạ sang 'a' — vi phạm tính song ánh (hai ký tự nguồn khác nhau phải ánh xạ tới hai ký tự đích khác nhau).

Hai map giải quyết

Map ngược t2s kiểm tra: nếu 'a' đã ánh xạ ngược về 'a', thì 'b' không thể cũng ánh xạ vào 'a'.

3.6 Worked Example 7 — Word Pattern

Đề (LeetCode #290): Pattern dạng "abba". String "dog cat cat dog". Trả True nếu pattern khớp với chuỗi từ qua một bijection.

Đây chính là Isomorphic Strings nâng lên cấp từ thay vì cấp ký tự.

def wordPattern(pattern, s):
    words = s.split()
    if len(pattern) != len(words): return False
    p2w, w2p = {}, {}
    for p, w in zip(pattern, words):
        if p in p2w and p2w[p] != w: return False
        if w in w2p and w2p[w] != p: return False
        p2w[p] = w
        w2p[w] = p
    return True

Trace

pattern = "abba", s = "dog cat cat dog"
('a','dog') → p2w={'a':'dog'}, w2p={'dog':'a'}
('b','cat') → p2w={'a':'dog','b':'cat'}, w2p={'dog':'a','cat':'b'}
('b','cat') → p2w['b'] == 'cat' ✓, w2p['cat'] == 'b' ✓
('a','dog') → khớp ✓
→ True

Knowledge Check — Lookup Pattern

4.1 Pattern Set Membership

set nhẹ hơn dict — không cần value. Dùng khi chỉ quan tâm "phần tử này có trong tập đã thấy không?".

Tín hiệu

• Phát hiện chu kỳ (cycle): "đã từng thăm chưa?".
• Tìm phần tử thoả điều kiện so với tập gốc (Longest Consecutive Sequence).
• Loại bỏ duplicate trong set operations (giao, hợp, hiệu).

Operations cốt lõi

s = set()
s.add(x)          # O(1)
x in s            # O(1)
s.remove(x)       # O(1) — lỗi nếu x không có
s.discard(x)      # O(1) — không lỗi
a & b             # giao (intersection)
a | b             # hợp (union)
a - b             # hiệu

4.2 Worked Example 8 — Longest Consecutive Sequence

Đề (LeetCode #128): Mảng nums chưa sort. Tìm độ dài chuỗi liên tiếp dài nhất.

Ví dụ: [100,4,200,1,3,2] → 4 (chuỗi 1,2,3,4). Yêu cầu O(n).

Approach ngây thơ — Sort

Sort rồi duyệt → O(n log n). Vi phạm yêu cầu.

Approach Set + Trick "chỉ start ở đầu chuỗi"

def longestConsecutive(nums):
    s = set(nums)
    longest = 0
    for x in s:
        if x - 1 not in s:               # x là đầu chuỗi
            length = 1
            while x + length in s:
                length += 1
            longest = max(longest, length)
    return longest

Time O(n), Space O(n).

4.3 LCS — Vì sao trick "chỉ start ở đầu chuỗi" đảm bảo O(n)?

Lo lắng tự nhiên: vòng while x + length in s có thể chạy lâu — sao tổng thời gian là O(n)?

Lập luận amortised

Vòng while chỉ chạy khi x là đầu chuỗi (x - 1 not in s).

Khi đó, vòng đếm chính xác độ dài của chuỗi mà x mở đầu — gọi là L. Vòng tốn O(L).

Mỗi phần tử của nums thuộc đúng một chuỗi liên tiếp duy nhất, nên tổng L qua tất cả các "đầu chuỗi" = n.

Trace với [100, 4, 200, 1, 3, 2]

• x = 100: 99 ∉ s → start. While: 101 ∉ s → length = 1.
• x = 4: 3 ∈ s → skip (không phải đầu chuỗi).
• x = 200: 199 ∉ s → start. length = 1.
• x = 1: 0 ∉ s → start. While: 2,3,4 ∈ s; 5 ∉ s → length = 4.
• x = 3: 2 ∈ s → skip.
• x = 2: 1 ∈ s → skip.

Kết quả: 4.

4.4 Worked Example 9 — Happy Number (Set Cycle Detection)

Đề (LeetCode #202): Số n là "happy" nếu lặp lại quá trình "thay n bằng tổng bình phương các chữ số" cuối cùng cho ra 1. Nếu chu kỳ vô hạn không chứa 1 → False.

Ví dụ: 19 → 1²+9² = 82 → 8²+2² = 68 → 6²+8² = 100 → 1²+0²+0² = 1 → True.

Pattern: Set lưu các số đã gặp để detect cycle

def isHappy(n):
    def step(x):
        s = 0
        while x:
            x, d = divmod(x, 10)
            s += d * d
        return s

    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = step(n)
    return n == 1

Time và space phụ thuộc vào số chu kỳ — chứng minh được là O(log n) dựa trên phân tích các giá trị đạt được.

Knowledge Check — Set Membership

5.1 Combo: Hash + Prefix Sum (review #560)

Đã làm chi tiết ở Tuần 2. Ôn lại nhanh tinh thần kết hợp:

def subarraySum(nums, k):
    count, prefix = 0, 0
    seen = defaultdict(int)
    seen[0] = 1
    for x in nums:
        prefix += x
        count += seen[prefix - k]
        seen[prefix] += 1
    return count

• Prefix sum biến điều kiện về subarray thành hiệu hai prefix.
• Hash tra cứu nhanh prefix cần tìm.
• Kết quả: O(n) thay vì O(n²) brute force.

5.2 Worked Example 10 — Longest Substring Without Repeating Characters

Đề (LeetCode #3): String s. Tìm độ dài substring dài nhất không có ký tự lặp.

Đây là cầu nối hoàn hảo từ Hash sang Sliding Window (Tuần 4).

def lengthOfLongestSubstring(s):
    last_seen = {}                       # ký tự → index gần nhất
    longest = 0
    left = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1     # đẩy left qua ký tự lặp
        last_seen[ch] = right
        longest = max(longest, right - left + 1)
    return longest

Trace với "abcabcbb"

5.3 Decision Tree mở rộng — Hashing trong bức tranh lớn

Tổng kết Tuần 3

Đã học

• Cơ chế hash: O(1) trung bình, O(n) worst case; load factor; collision.
• Ba cấu trúc: dict, set, Counter — và operations multiset của Counter.
• Key Design: tuple đếm, sorted string, frozenset — chọn key biểu diễn duy nhất đặc trưng cần so sánh.
• Frequency Pattern: đếm trước, xử lý sau (2-pass), bucket sort.
• Lookup Pattern: O(n²) → O(n); two-way lookup cho bijection.
• Set Membership: cycle detection, smart "đầu chuỗi" trick.
• Combo: Hash + Prefix, Hash + Sliding Window (mở đường Tuần 4).

Bài về nhà (12 bài)

1. LeetCode #49 — Group Anagrams
2. LeetCode #347 — Top K Frequent Elements (cả 3 approach)
3. LeetCode #387 — First Unique Character in a String
4. LeetCode #1002 — Find Common Characters
5. LeetCode #219 — Contains Duplicate II
6. LeetCode #205 — Isomorphic Strings
7. LeetCode #290 — Word Pattern
8. LeetCode #128 — Longest Consecutive Sequence
9. LeetCode #202 — Happy Number
10. LeetCode #3 — Longest Substring Without Repeating Characters
11. LeetCode #383 — Ransom Note (Counter subtraction)
12. LeetCode #1 — Two Sum (code lại lần 2 — kiểm tra retention)