Permutation in String: cửa sổ cố định kích thước với đếm ký tự khớp nhau

Một permutation của s1 là bất kỳ cách sắp xếp lại nào của các ký tự trong đó. "ab" cho ra "ba" và "ab" — đó là hai permutation. Bài toán hỏi: liệu s2 có chứa bất kỳ permutation nào trong số đó như một substring liên tiếp không?

Cách nhìn lại vấn đề: permutation chính là anagram. Hai chuỗi là anagram khi và chỉ khi chúng có tần số ký tự giống hệt nhau. Vậy câu hỏi thực ra là: liệu có window nào có độ dài len(s1) trong s2 có cùng frequency histogram với s1 không? Cách nhìn đó làm cho thuật toán gần như hiển nhiên. Cố định kích thước window ở len(s1), trượt qua s2 từng bước một, và kiểm tra tần số ở mỗi vị trí.

Constraints buộc ta phải làm gì

Cả hai chuỗi có độ dài tối đa 10^4 và chỉ gồm chữ cái thường. Ba điều rút ra từ đó.

Constraint "chỉ chữ thường" là hữu ích nhất. Frequency histogram chỉ có đúng 26 slot. Ta có thể dùng array cố định kích thước 26 thay vì hash map, biến phép so sánh O(k) thành O(26) = O(1), đồng thời loại bỏ hoàn toàn vấn đề phải xóa key khỏi dictionary (slot array luôn tồn tại, không cần xóa).

Giới hạn 10^4 loại trừ solution O(n^2). Với cả hai chuỗi ở độ dài tối đa, brute force cho khoảng 10^8 phép toán — về mặt lý thuyết còn chịu được, nhưng O(n) sliding window là approach được thiết kế cho bài này. Gợi ý đầu tiên của đề bài thậm chí nói thẳng "brute force sẽ TLE".

Constraint quan trọng hơn ít ai để ý: permutation có cùng độ dài với chuỗi gốc — không ngắn hơn, không dài hơn. Điều đó có nghĩa là kích thước window bị khóa ở len(s1) ngay từ đầu. Đây không phải bài toán variable-window mà ta phải tìm kích thước phù hợp; input đã cho sẵn. Điểm đó phân biệt bài này với Minimum Window Substring (76), nơi kích thước window thay đổi.

Brute force: O(n x m)

Cách đọc đơn giản nhất: với mỗi starting index i trong s2, trích xuất substring s2[i : i + len(s1)] và so sánh character count của nó với s1.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
 
        def freq(s):
            count = {}
            for c in s:
                count[c] = count.get(c, 0) + 1
            return count
 
        s1_freq = freq(s1)
        k = len(s1)
 
        for i in range(len(s2) - k + 1):
            if freq(s2[i:i + k]) == s1_freq:
                return True
 
        return False

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        if (s1.Length > s2.Length) return false;
 
        Dictionary<char, int> FreqOf(string s) {
            var d = new Dictionary<char, int>();
            foreach (char c in s) d[c] = d.GetValueOrDefault(c, 0) + 1;
            return d;
        }
 
        var s1Freq = FreqOf(s1);
        int k = s1.Length;
 
        for (int i = 0; i <= s2.Length - k; i++) {
            if (FreqOf(s2.Substring(i, k)).SequenceEqual(s1Freq))
                return true;
        }
 
        return false;
    }
}

Time: O(n x m) — với mỗi n - m + 1 window, xây frequency map tốn O(m). Space: O(m) cho map. Nó hoạt động, nhưng nó vứt bỏ toàn bộ thông tin tần số ở mỗi bước rồi xây lại từ đầu. Hai window liền kề chia sẻ m - 1 ký tự — ta đang tính lại chúng mỗi lần.

Thử từng bước với ví dụ 1: s1 = "ab", s2 = "eidbaooo", window size k = 2.

• i = 0, window "ei": freq {e:1, i:1} != {a:1, b:1}
• i = 1, window "id": freq {i:1, d:1} != {a:1, b:1}
• i = 2, window "db": freq {d:1, b:1} != {a:1, b:1}
• i = 3, window "ba": freq {b:1, a:1} == {a:1, b:1} -> return true

Tìm ra đáp án, chỉ là chậm. Chú ý bước 2 -> 3: ta bỏ 'i' và 'd', thêm 'b'. Ta phải đếm lại tất cả, dù 'b' đã nhìn thấy từ bước 2. Đó là phần lãng phí.

Sliding window với hai frequency map: O(n)

Thay vì xây lại, duy trì một running frequency map cho window hiện tại. Khi window tiến một bước, thêm một ký tự bên phải và xóa một ký tự bên trái. Map thay đổi dần — O(1) mỗi bước.

Sơ đồ trạng thái dưới đây theo dõi cùng ví dụ đó, cho thấy chính xác cách window và frequency map của nó thay đổi:

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
 
        k = len(s1)
        s1_freq = {}
        for c in s1:
            s1_freq[c] = s1_freq.get(c, 0) + 1
 
        window = {}
        for c in s2[:k]:
            window[c] = window.get(c, 0) + 1
 
        if window == s1_freq:
            return True
 
        for i in range(k, len(s2)):
            # Thêm ký tự bên phải
            right = s2[i]
            window[right] = window.get(right, 0) + 1
 
            # Xóa ký tự bên trái
            left = s2[i - k]
            window[left] -= 1
            if window[left] == 0:
                del window[left]
 
            if window == s1_freq:
                return True
 
        return False

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        if (s1.Length > s2.Length) return false;
 
        int k = s1.Length;
        var s1Freq = new Dictionary<char, int>();
        foreach (char c in s1) s1Freq[c] = s1Freq.GetValueOrDefault(c, 0) + 1;
 
        var window = new Dictionary<char, int>();
        for (int i = 0; i < k; i++)
            window[s2[i]] = window.GetValueOrDefault(s2[i], 0) + 1;
 
        if (DictEqual(window, s1Freq)) return true;
 
        for (int i = k; i < s2.Length; i++) {
            char right = s2[i];
            window[right] = window.GetValueOrDefault(right, 0) + 1;
 
            char left = s2[i - k];
            window[left]--;
            if (window[left] == 0) window.Remove(left);
 
            if (DictEqual(window, s1Freq)) return true;
        }
 
        return false;
    }
 
    private bool DictEqual(Dictionary<char, int> a, Dictionary<char, int> b) {
        if (a.Count != b.Count) return false;
        foreach (var kv in a)
            if (!b.TryGetValue(kv.Key, out int v) || v != kv.Value) return false;
        return true;
    }
}

Time: O(n + m). Khởi tạo là O(m); mỗi bước slide là O(1) cho map update. So sánh dict == chạy trong O(26) = O(1) vì alphabet bị giới hạn. Space: O(1) thực tế — các map chứa tối đa 26 entry.

Hãy theo dõi toàn bộ trạng thái với s1 = "ab", s2 = "eidbaooo":

Ban đầu: s1_freq = {a:1, b:1}
Xây window[0:2] = "ei": window = {e:1, i:1}
window == s1_freq? Không -> vào vòng lặp

i=2: right='d', left='e'
  thêm 'd': window = {e:1, i:1, d:1}
  xóa 'e': window = {i:1, d:1}   (e xóa vì count -> 0)
  window == s1_freq? {i:1,d:1} != {a:1,b:1} Không

i=3: right='b', left='i'
  thêm 'b': window = {i:1, d:1, b:1}
  xóa 'i': window = {d:1, b:1}   (i xóa)
  window == s1_freq? {d:1,b:1} != {a:1,b:1} Không

i=4: right='a', left='d'
  thêm 'a': window = {d:1, b:1, a:1}
  xóa 'd': window = {b:1, a:1}   (d xóa)
  window == s1_freq? {b:1,a:1} == {a:1,b:1} Có -> return True

Mỗi del window[left] chỉ xảy ra khi count của ký tự đó về đúng bằng không. Đó là invariant: dict không bao giờ chứa key có giá trị 0, nên phép kiểm tra equality không bao giờ bị đánh lừa bởi entry ảo.

Một bẫy thường gặp: quên xóa key khi count về 0. Để lại số 0 trong map và kiểm tra equality sẽ sai — s1_freq không có key đó, window có, chúng trông không bằng nhau dù window thực ra là permutation hợp lệ. Đây là bug phổ biến nhất của approach này.

Tối ưu với array: O(n) gọn hơn

Constraints nói chuỗi chỉ gồm chữ thường. Điều đó có nghĩa là ta bỏ hash map hoàn toàn và dùng hai array cố định kích thước 26. So sánh array trong Python (== trên list) và một vòng lặp đơn giản trong C# — cả hai đều O(26) = O(1).

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
 
        s1_count = [0] * 26
        window_count = [0] * 26
 
        # Xây s1 frequency và initial window cùng lúc
        for i in range(len(s1)):
            s1_count[ord(s1[i]) - ord('a')] += 1
            window_count[ord(s2[i]) - ord('a')] += 1
 
        if s1_count == window_count:
            return True
 
        for i in range(len(s1), len(s2)):
            # Thêm ký tự bên phải
            window_count[ord(s2[i]) - ord('a')] += 1
            # Xóa ký tự bên trái
            window_count[ord(s2[i - len(s1)]) - ord('a')] -= 1
 
            if window_count == s1_count:
                return True
 
        return False

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        if (s1.Length > s2.Length) return false;
 
        int[] s1Count = new int[26];
        int[] windowCount = new int[26];
 
        for (int i = 0; i < s1.Length; i++) {
            s1Count[s1[i] - 'a']++;
            windowCount[s2[i] - 'a']++;
        }
 
        if (ArrayEqual(s1Count, windowCount)) return true;
 
        for (int i = s1.Length; i < s2.Length; i++) {
            windowCount[s2[i] - 'a']++;
            windowCount[s2[i - s1.Length] - 'a']--;
 
            if (ArrayEqual(s1Count, windowCount)) return true;
        }
 
        return false;
    }
 
    private bool ArrayEqual(int[] a, int[] b) {
        for (int i = 0; i < 26; i++)
            if (a[i] != b[i]) return false;
        return true;
    }
}

Không cần xóa key. Không cần kiểm tra key tồn tại không. Các slot array có thể âm — cụ thể là window_count[c] có thể giảm xuống dưới 0 khi xóa trước khi một phép thêm tương ứng đưa nó trở lại — và điều đó không sao, vì equality chỉ thỏa mãn khi tất cả 26 slot khớp chính xác. Sạch hơn dict version và nhanh hơn một chút trong thực tế nhờ cache locality tốt hơn trên 26 số nguyên liên tiếp so với hash table.

Diff counter: version tôi sẽ submit

Cả hai array có 26 slot. So sánh chúng mỗi bước tốn O(26) — ổn thôi, nhưng có thể làm tốt hơn. Duy trì một số nguyên diff đếm xem có bao nhiêu trong 26 vị trí hiện đang không khớp giữa s1_freq và window. Khi diff == 0, tất cả vị trí khớp và ta tìm được permutation.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
 
        k = len(s1)
        s1_freq = [0] * 26
        window = [0] * 26
 
        for c in s1:
            s1_freq[ord(c) - ord('a')] += 1
 
        for c in s2[:k]:
            window[ord(c) - ord('a')] += 1
 
        # Đếm các vị trí mà hai array khác nhau
        diff = sum(1 for i in range(26) if s1_freq[i] != window[i])
 
        if diff == 0:
            return True
 
        for i in range(k, len(s2)):
            right = ord(s2[i]) - ord('a')
            left = ord(s2[i - k]) - ord('a')
 
            # Thêm ký tự bên phải
            if window[right] == s1_freq[right]:
                diff += 1      # đang khớp, sắp không khớp
            window[right] += 1
            if window[right] == s1_freq[right]:
                diff -= 1      # vừa khớp lại
 
            # Xóa ký tự bên trái
            if window[left] == s1_freq[left]:
                diff += 1
            window[left] -= 1
            if window[left] == s1_freq[left]:
                diff -= 1
 
            if diff == 0:
                return True
 
        return False

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        if (s1.Length > s2.Length) return false;
 
        int k = s1.Length;
        int[] s1Freq = new int[26];
        int[] window = new int[26];
 
        foreach (char c in s1) s1Freq[c - 'a']++;
        for (int i = 0; i < k; i++) window[s2[i] - 'a']++;
 
        int diff = 0;
        for (int i = 0; i < 26; i++)
            if (s1Freq[i] != window[i]) diff++;
 
        if (diff == 0) return true;
 
        for (int i = k; i < s2.Length; i++) {
            int right = s2[i] - 'a';
            int left = s2[i - k] - 'a';
 
            if (window[right] == s1Freq[right]) diff++;
            window[right]++;
            if (window[right] == s1Freq[right]) diff--;
 
            if (window[left] == s1Freq[left]) diff++;
            window[left]--;
            if (window[left] == s1Freq[left]) diff--;
 
            if (diff == 0) return true;
        }
 
        return false;
    }
}

Mỗi bước chạm đúng hai ký tự — right và left — và cập nhật diff với tối đa bốn phép so sánh. Kiểm tra match chỉ là một phép so sánh số nguyên. Không có map, không có bookkeeping xóa key, không có phép so sánh key phức tạp.

Logic cho mỗi ký tự: trước khi update, kiểm tra xem ký tự đó có đang đóng góp vào diff không. Nếu nó đang khớp (window[c] == s1_freq[c]), thay đổi sắp tới sẽ phá vỡ khớp đó — tăng diff. Thực hiện update. Sau đó kiểm tra xem update có tình cờ tạo ra khớp mới không — giảm diff. Pattern này hoạt động giống hệt cho cả thêm lẫn xóa.

Tại sao điều này đúng: diff chỉ thay đổi khi một slot vượt qua ngưỡng khớp. Nếu window[right] đang bằng s1_freq[right], một phép tăng sẽ đẩy nó ra xa — diff tăng. Nếu sau khi tăng chúng bằng nhau lại, diff giảm. Logic tự nhất quán.

Tại sao fixed-size đơn giản hơn variable

Series này đã đề cập cả hai kiểu sliding window. Trong Longest Repeating Character Replacement (424), kích thước window thay đổi — ta mở rộng bên phải khi điều kiện cho phép và co lại từ trái khi không. Window co lại để khôi phục một thuộc tính.

Ở đây không có co lại. Kích thước window được ghim ở len(s1) trong suốt quá trình chạy. Nó tiến đúng một bước mỗi lần — right pointer và left pointer di chuyển đồng bộ. Đó là đặc trưng của bài toán fixed-size window: kích thước được input cho sẵn, không phải do thuật toán tìm ra.

Cấu trúc này hợp lý. Permutation có cùng độ dài với chuỗi gốc. Bất kỳ window nào ngắn hơn hoặc dài hơn đều không thể là permutation của s1. Window chỉ có thể đúng bằng len(s1) ký tự.

So sánh các approach

*O(1) vì alphabet bị giới hạn 26 ký tự.

Edge case đáng kiểm tra

len(s1) > len(s2) — trả về false ngay. Không có vị trí window hợp lệ nào; bounds vòng lặp range(len(s2) - k + 1) vốn dĩ đã rỗng, nhưng early return thể hiện rõ ý định hơn.

s1 == s2 — window duy nhất chính là s2. Initial window check trước vòng lặp xử lý điều này. Thiếu bước kiểm tra đó, range(k, len(s2)) sẽ rỗng và hàm trả về false sai.

s1 = "a", s2 = "ab" — permutation ở index 0. Window ban đầu là s2[:1] = "a", khớp với s1_freq = {a:1}. Bắt được trước khi vòng lặp bắt đầu.

s1 = "ab", s2 = "ba" — len(s1) == len(s2), nên toàn bộ s2 là window duy nhất. Cũng bị bắt bởi initial check.

Toàn ký tự giống nhau, s1 = "aaa", s2 = "aaaa" — mọi window kích thước 3 đều có freq {a:3} và s1_freq là {a:3}. Window đầu tiên khớp ngay. Không có gì đặc biệt trong code; chỉ xác nhận rằng frequency comparison vẫn hoạt động đúng khi chỉ có một ký tự duy nhất.

Initial window check trước vòng lặp không phải tùy chọn. Nếu s1.length == s2.length, thân vòng lặp không bao giờ chạy — không có giá trị i hợp lệ trong range(k, len(s2)). Thiếu kiểm tra trước vòng lặp, ta sẽ trả về false sai khi s2 chính là permutation.

Nhận diện pattern

Các keyword nên kích hoạt approach này: "permutation", "anagram", "substring contains", "rearrangement". Bất cứ khi nào bài toán hỏi liệu một cách sắp xếp lại của chuỗi có độ dài cố định có xuất hiện bên trong chuỗi khác không, hình dạng luôn là: fixed-size sliding window cộng với character frequency comparison.

Cách đặt vấn đề permutation/anagram là bẫy nếu bạn cố enumerate tất cả permutation. Có đến m! permutation của s1 — với m = 10 là 3.6 triệu. Frequency comparison gộp tất cả chúng lại thành một phép kiểm tra O(1) cho mỗi vị trí window. Đây là mental model đáng nhớ: permutation membership == frequency histogram equality. Một cách nhìn đó mở khóa toàn bộ lớp bài toán này.

Version nào nên viết

Version dict với hai frequency map rõ ràng nhất để viết trong phỏng vấn — ý định hiển nhiên và bước xóa key buộc ta phải suy nghĩ về invariant. Bắt đầu với cái đó.

Array version là thứ ta chọn khi nhận ra constraint chữ thường. Không cần xóa, logic đơn giản hơn, nhanh hơn trong thực tế.

Diff counter là thứ tôi sẽ submit sau khi array version đã chạy được. Nó làm invariant — "có bao nhiêu vị trí đang sai" — trở nên tường minh thay vì ẩn bên trong phép so sánh array. Một số nguyên, bốn phép so sánh mỗi bước, xong.

Các bài liên quan

Find All Anagrams in a String (438) là extension trực tiếp: thay vì trả về true khi tìm match đầu tiên, thu thập mọi starting index có match. Window mechanics giống hệt — thay early return bằng thêm vào list. Twist: không thể return sớm, nên luôn phải quét hết chuỗi.

Minimum Window Substring (76) là người anh em variable-size. Không còn tìm window có độ dài chính xác nữa — muốn window nhỏ nhất trong s2 chứa tất cả ký tự của s1 (có lặp lại). Ý tưởng diff counter vẫn áp dụng được, nhưng left pointer di chuyển độc lập, co window lại mỗi khi tất cả ký tự đã được thỏa mãn.

Valid Anagram (242) là bài warmup đơn giản hơn: cho hai chuỗi có cùng độ dài, kiểm tra một cái có phải anagram của cái kia không. Không cần sliding window — chỉ cần một phép so sánh frequency.

Longest Substring Without Repeating Characters (3) dùng variable-size window khác, với constraint là ký tự phải unique thay vì frequency phải khớp. Đây là bài tương phản tốt để thấy fixed và variable window khác cấu trúc như thế nào.