Cho chuỗi i (chữ thường) và số nguyên j. Đếm số chuỗi có độ dài bằng i, từ điển ≤ i, và không có hơn j ký tự liên tiếp giống nhau. Kết quả modulo 10^9+7.
Ví dụ: i = "app", j = 2 → 405.
Giải pháp
DP với memoization (digit DP):
- dp(pos, bound, last, count): số cách từ vị trí pos
- bound: có bị giới hạn bởi chuỗi gốc không
- last: ký tự trước (0-25, -1 cho chưa có)
- count: số ký tự liên tiếp giống last
- Nếu count > j: trả về 0
- Nếu pos == n: trả về 1
- Duyệt ký tự tiếp theo từ 0 đến (num[pos] nếu bound else 25)
- Cập nhật bound, last, count tương ứng
Ví dụ minh họa
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]
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))
Đầu vào
i = "app" j = 2
Đầu ra
405