पायथन में समान आकार के स्ट्रिंग्स ज्ञात करने का प्रोग्राम

मान लीजिए, हमारे पास लोअरकेस अक्षरों से युक्त एक स्ट्रिंग 'i' और एक अन्य पूर्णांक 'j' है। हमें यह ज्ञात करना है कि कितनी स्ट्रिंग्स हैं जो 'i' के आकार के बराबर हैं और लेक्सिकोग्राफिक रूप से 'i' से छोटी या बराबर हैं और जिनमें 'j' से अधिक लगातार समान वर्ण नहीं हैं।

उत्तर की गणना परिणाम को 10^9 + 7 से मोड करके की जानी है।

इसलिए, यदि इनपुट i = "app", j = 2 जैसा है, तो आउटपुट 405 होगा।

हल करने के चरण

यदि j <= 0, तो 0 लौटाएं
m := 10^9 + 7
n := i का आकार
nums := एक नई सूची जिसमें s में मौजूद प्रत्येक वर्ण के लिए (यूनिकोड प्रतिनिधित्व - "a" का यूनिकोड प्रतिनिधित्व) हो
dp(0, True, -1, 0) mod m लौटाएं
dp() फ़ंक्शन परिभाषित करें। यह pos, bound, last, count लेगा
- यदि count > j शून्येतर है, तो 0 लौटाएं
- यदि pos, n के समान है, तो 1 लौटाएं
- num := nums[pos]
- res := 0
- i के लिए 0 से (num + 1 यदि bound अन्यथा 26) तक की रेंज में, करें
  - res := res + dp(pos + 1, bound और i, num के समान है, i, count * (i, last के समान है) + 1)
- res लौटाएं
मुख्य विधि से dp(0, True, -1, 0) % m लौटाएं

उदाहरण

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