โปรแกรมหาจำนวนสตริงขนาดเท่ากันที่ lexicographically น้อยกว่าหรือเท่าและไม่มีตัวอักษรซ้ำติดกันเกิน j ใน Python

คำอธิบายโจทย์

ให้สตริง i และจำนวนเต็ม j หาจำนวนสตริงที่มีความยาวเท่า i, ≤ i แบบ lexicographic, และไม่มีตัวอักษรติดกันซ้ำกัน > j ตัว ตอบ mod 10^9+7

ตัวอย่าง

i = "app", j = 2 → 405

วิธีแก้ปัญหา

Digit DP (String DP) + Memoization:

1. dp(pos, bound, last_char, consecutive_count)
2. pos: ตำแหน่งปัจจุบัน, bound: ยังติดขอบเขต i หรือไม่
3. last_char: ตัวอักษรก่อนหน้า (-1 = เริ่มต้น), consecutive_count: จำนวนติดกัน
4. ถ้า count > j → 0 (invalid)
5. ลองตัวอักษร 0..(num ถ้า bound else 25)

โค้ด Python

class Solution:
    def solve(self, s, k):
        if k <= 0:
            return 0
        MOD = 10**9 + 7
        n = len(s)
        nums = [ord(char) - ord("a") for char in s]
        
        from functools import lru_cache
        
        @lru_cache(None)
        def dp(pos, bound, last, count):
            if count > k:
                return 0
            if pos == n:
                return 1
            num = nums[pos]
            res = 0
            for i in range(num + 1 if bound else 26):
                res += dp(pos + 1, bound and i == num, i, count * (i == last) + 1)
            return res
        
        return dp(0, True, -1, 0) % MOD

ob = Solution()
print(ob.solve('app', 2))

อินพุต

i = "app" j = 2

เอาต์พุต

405