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

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

res :=केवल एक तत्व 0 के साथ एक सूची
एक फ़ंक्शन को परिभाषित करें dfs() । यह s, पथ लेगा जो एक नया खाली सेट है
अगर s खाली है, तो
- res[0] :=अधिकतम रेस [0] और पथ का आकार
- वापसी
i श्रेणी 1 से s के आकार के लिए, करें
- x :=s का उप-सरणी [सूचकांक 0 से i-1 तक]
- यदि x पथ में नहीं है, तो
  - dfs(s का सबस्ट्रिंग [इंडेक्स i से अंत तक], पथ U {x})
मुख्य विधि से निम्न कार्य करें -
dfs)
रिटर्न रेस[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"