Can Make Palindrome From Substring: Xác Định Substring Có Thể Sắp Xếp Thành Palindrome Sau K Thay Thay Thế

Đề bài: Cho string s và mảng query queries[i] = [left, right, k]. Với substring s[left:right+1], ta được phép sắp xếp lại và thay thế tối đa k ký tự. Hỏi có thể biến thành palindrome không? Trả về mảng boolean.

Ví dụ: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]] → [True, False, False, True, True]

Quan sát quan trọng

Một string có thể sắp xếp thành palindrome khi và chỉ khi số ký tự xuất hiện lẻ ≤ 1 (cho độ dài lẻ) hoặc = 0 (cho độ dài chẵn). Mỗi phép thay thế có thể giảm 2 ký tự lẻ (thay 1 ký tự lẻ thành ký tự khác khớp cặp). Do đó cần: (số ký tự lẻ) // 2 ≤ k.

Thuật toán: Prefix Sum + Bitmask (Tối ưu O(1) mỗi query)

1. Tính prefix frequency: dp[i][c] = số lần ký tự c xuất hiện trong s[:i].
2. Với query [l, r, k]: tần suất ký tự c trong substring = dp[r+1][c] - dp[l][c].
3. Đếm số ký tự có tần suất lẻ: odd = sum((freq % 2) for freq in ...).
4. Kết quả: odd // 2 <= k.

Code Python

class Solution:
    def canMakePaliQueries(self, s: str, queries: list[list[int]]) -> list[bool]:
        n = len(s)
        # dp[i][c]: tần suất ký tự c trong s[:i] (i từ 0 đến n)
        dp = [[0] * 26 for _ in range(n + 1)]
        
        for i in range(1, n + 1):
            for c in range(26):
                dp[i][c] = dp[i-1][c]
            dp[i][ord(s[i-1]) - ord('a')] += 1
        
        res = []
        for l, r, k in queries:
            l += 1  # chuyển sang 1-based cho dp
            r += 1
            odd = 0
            for c in range(26):
                freq = dp[r][c] - dp[l-1][c]
                odd += freq % 2
            res.append(odd // 2 <= k)
        
        return res

# Test
ob = Solution()
print(ob.canMakePaliQueries("abcda", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]))
# [True, False, False, True, True]

Tối ưu hóa thêm: Bitmask (O(1) space per prefix)

Thay vì mảng 26 phần tử, dùng 1 integer 26-bit. Bit i = 1 nếu tần suất ký tự i lẻ. XOR prefix để lấy odd count trong O(1).

class Solution:
    def canMakePaliQueries(self, s: str, queries: list[list[int]]) -> list[bool]:
        n = len(s)
        prefix = [0] * (n + 1)
        for i, ch in enumerate(s, 1):
            bit = 1 << (ord(ch) - ord('a'))
            prefix[i] = prefix[i-1] ^ bit
        
        res = []
        for l, r, k in queries:
            mask = prefix[r+1] ^ prefix[l]
            odd = mask.bit_count()  # Python 3.8+: bin(mask).count('1')
            res.append(odd // 2 <= k)
        return res

Kết luận

Prefix sum + bitmask là giải pháp tối ưu cho nhiều query. Hiểu bản chất palindrome (số ký tự lẻ) là chìa khóa.