পাইথনে দিয়ে गये স্ট্রিংয়ের সাইজ ও কন্ডিশন মেনে স্ট্রিং গণনা (Mod 10^9+7)

একটি স্ট্রিং i (লোয়ারকেস) এবং ইন্টিজার j দেওয়া আছে। i-এর সাইজের এবং লেক্সিকোগ্রাফিক্যালি i-এর চেয়ে ছোট বা সমান এবং কোনো ক্যারেক্টার j এর চেয়ে বেশি বারрядেই কনসিকিউটিভ নয় — এমন স্ট্রিং কতটি আছে তা বের করতে হবে। ফলাফল 10^9+7 দিয়ে মডুলো।

উদাহরণ: i = "app", j = 2 → আউটপুট 405।

সমাধানের ধাপসমূহ (ডিজিট DP / মেমোরাইজেশন)

যদি k <= 0 হয়, ০ রিটার্ন করুন।
MOD := 10^9+7, n := len(s)।
nums := স্ট্রিংয়ের প্রতিটি ক্যারেক্টারের ('a' থেকে দূরত্ব) অ্যারে।
dp(pos, bound, last, count) ফাংশন:
- যদি count > k, ০ রিটার্ন।
- যদি pos == n, ১ রিটার্ন।
- num = nums[pos]।
- res = 0। i = 0 থেকে (num if bound else 25) পর্যন্ত লুপ:
  - res += dp(pos+1, bound and i==num, i, count*(i==last)+1)
- res রিটার্ন করুন।
dp(0, True, -1, 0) % MOD রিটার্ন করুন।

পাইথন কোড উদাহরণ

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))

ইনপুট

i = "app" j = 2