Python में स्ट्रिंग को अधिकतम अद्वितीय सबस्ट्रिंग में विभाजित करने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें वह अधिकतम संख्या ढूंढनी है जिसमें दी गई स्ट्रिंग को अद्वितीय सबस्ट्रिंग में विभाजित किया जा सकता है। हम स्ट्रिंग s को नॉन-खाली सबस्ट्रिंग की किसी भी सूची में विभाजित कर सकते हैं जैसे कि सबस्ट्रिंग का कन्केटनेशन मूल स्ट्रिंग बनाता है। लेकिन हमें सबस्ट्रिंग को इस तरह विभाजित करना होगा कि उनमें से सभी समान हों।

उदाहरण के लिए, यदि इनपुट है s = "pqpqrrr", तो आउटपुट 5 होगा क्योंकि हम इसे ['p', 'q', 'pq', 'r', 'rr'] की तरह विभाजित कर सकते हैं। यदि हम ['p', 'q', 'p', 'q', 'r', 'rr'] की तरह विभाजित करते हैं तो यह मान्य नहीं है क्योंकि यहां 'p' और 'q' कई बार मौजूद हैं।

समाधान के चरण

1. res := [0] (केवल एक तत्व 0 वाली सूची)
2. dfs() फंक्शन परिभाषित करें जो s, path लेता है जो एक नया खाली सेट है
3. यदि s खाली है:
   • res[0] := max(res[0], len(path))
   • वापस करें
4. i को 1 से len(s) तक:
   • x := s[:i]
   • यदि x not in path:
     • dfs(s[i:], path | {x})
5. मुख्य मेथड से:
   • dfs(s)
   • res[0] वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(s):
    res = [0]
    def dfs(s, path=set()):
        if not s:
            res[0] = max(res[0], len(path))
            return
        for i in range(1, len(s)+1):
            x = s[:i]
            if x not in path:
                dfs(s[i:], path | {x})
    dfs(s)
    return res[0]

s = "pqpqrrr"
print(solve(s))

इनपुट

"pqpqrrr"

आउटपुट

5