पायथन में कम से कम k बार आने वाले वर्णों वाले सबसे लंबे सबस्ट्रिंग की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है जहां प्रत्येक वर्ण सॉर्टेड है और हमारे पास एक संख्या k भी है, हमें सबसे लंबे सबस्ट्रिंग की लंबाई ढूंढनी है जैसे कि प्रत्येक वर्ण कम से कम k बार आता हो।

उदाहरण के लिए, यदि इनपुट s = "aabccddeeffghij" और k = 2 है, तो आउटपुट 8 होगा, क्योंकि यहां सबसे लंबा सबस्ट्रिंग "ccddeeff" है जहां प्रत्येक वर्ण कम से कम 2 बार आता है।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (डिवाइड एंड कंकर):

एक फंक्शन rc() परिभाषित करें जो lst लेता है
c := सभी वर्णों और उनकी घटनाओं वाला मैप
acc := एक नई सूची, ans := 0, valid := True
प्रत्येक x के लिए lst में:
- यदि c[x] < k:
  - valid := False
  - ans := max(ans, rc(acc))
  - acc := []
- अन्यथा:
  - x को acc के अंत में डालें
यदि valid सच है:
- len(acc) लौटाएं
अन्यथा:
- ans := max(ans, rc(acc))
- ans लौटाएं
मुख्य मेथड से: rc(list(s)) लौटाएं

उदाहरण कोड

from collections import Counter

class Solution:
    def solve(self, s, k):
        def rc(lst):
            c = Counter(lst)
            acc = []
            ans = 0
            valid = True
            for x in lst:
                if c[x] < k:
                    valid = False
                    ans = max(ans, rc(acc))
                    acc = []
                else:
                    acc.append(x)
            if valid:
                return len(acc)
            else:
                ans = max(ans, rc(acc))
                return ans
        return rc(list(s))

ob = Solution()
s = "aabccddeeffghij"
k = 2
print(ob.solve(s, k))

इनपुट

"aabccddeeffghij", 2