Can Make Palindrome from Substring: ตรวจสอบว่า Substring ทำเป็น Palindrome ได้หรือไม่

โจทย์

กำหนด string s และ queries หลายๆ query แต่ละ query = [left, right, k] หมายถึง substring s[left:right+1] เราสามารถ:

1. เรียงลำดับตัวอักษรใน substring ได้อย่างอิสระ
2. เปลี่ยนตัวอักษรได้สูงสุด k ตัว (เปลี่ยนเป็นตัวอักษร lowercase ใดๆ)

ถ้าสามารถทำให้เป็น palindrome ได้ → คืน true, มิฉะนั้น false

ตัวอย่าง: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]] → Output: [true, false, false, true, true]

ข้อสังเกตสำคัญ

Palindrome ต้องมีตัวอักษรที่มีความถี่คี่ (odd frequency) ไม่เกิน 1 ตัว (ตัวกลาง) ดังนั้น:

• นับความถี่ตัวอักษรใน substring
• นับจำนวนตัวอักษรที่มีความถี่คี่ = odd_count
• ต้องเปลี่ยนตัวอักษรอย่างน้อย odd_count // 2 ครั้ง เพื่อทำให้คี่เหลือ ≤ 1
• เงื่อนไข: odd_count // 2 <= k

การเพิ่มประสิทธิภาพ: Prefix Sum (DP)

สร้าง Prefix Frequency Array dp[i][c] = จำนวนตัวอักษร c ใน s[0:i] (1-indexed) เพื่อ query ความถี่ในช่วง O(1)

การติดตั้ง (Python Implementation)

class Solution:
    def canMakePaliQueries(self, s: str, queries: list[list[int]]) -> list[bool]:
        n = len(s)
        # dp[i][j] = count of char j in s[0:i] (1-indexed, dp[0] = all zeros)
        dp = [[0] * 26 for _ in range(n + 1)]
        
        # Build prefix sums
        for i in range(1, n + 1):
            for j in range(26):
                dp[i][j] = dp[i-1][j]
            dp[i][ord(s[i-1]) - ord('a')] += 1
        
        def solve(l: int, r: int, k: int) -> bool:
            # l, r เป็น 0-indexed, แปลงเป็น 1-indexed สำหรับ dp
            l += 1
            r += 1
            odd_count = 0
            for j in range(26):
                freq = dp[r][j] - dp[l-1][j]
                odd_count += freq % 2
            return (odd_count // 2) <= k
        
        return [solve(l, r, k) for l, r, k in queries]

# ทดสอบ
ob = Solution()
s = "abcda"
queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
print(ob.canMakePaliQueries(s, queries))
# [True, False, False, True, True]

Output

[True, False, False, True, True]

การวิเคราะห์ตัวอย่าง

Complexity

• Preprocessing: O(n × 26) = O(n)
• Per Query: O(26) = O(1)
• Total: O(n + q) - เหมาะสำหรับ queries จำนวนมาก

สรุป

ใช้ Prefix Sum (DP) เก็บความถี่สะสม ทำให้ query แต่ละอันทำได้ O(26) = O(1) เทคนิคนี้ใช้ได้กับโจทย์หลายรูปแบบที่ต้อง query ความถี่ในช่วงบ่อยๆ

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ