पायथन में अद्वितीय वर्णों वाले संयोजित स्ट्रिंग की अधिकतम लंबाई ढूंढने का प्रोग्राम

स्ट्रिंग्स की एक सूची words दी गई है। हमें शब्दों के एक उपअनुक्रम को संयोजित करके एक स्ट्रिंग बनानी है जिसमें प्रत्येक वर्ण अद्वितीय हो (कोई डुप्लिकेट नहीं)। ऐसे सबसे लंबे संयोजन की लंबाई वापस करनी है।

उदाहरण

इनपुट: words = ["xyz", "xyw", "wab", "cde"]

आउटपुट: 9

व्याख्या: हम "xyz" + "wab" + "cde" = "xyzwabcde" (लंबाई 9) चुन सकते हैं। सभी वर्ण अद्वितीय हैं।

एल्गोरिदम (बैकट्रैकिंग)

1. वैश्विक चर ans = 0 से शुरू करें।
2. एक सहायक फ़ंक्शन is_unique(s) परिभाषित करें जो जांचता है कि स्ट्रिंग s के सभी वर्ण अद्वितीय हैं या नहीं (सेट का उपयोग करके)।
3. पुनरावर्ती फ़ंक्शन recur(i, cur) परिभाषित करें:
   • यदि i == len(words): ans = max(ans, len(cur)) अपडेट करें और वापस लौटें।
   • वर्तमान शब्द को छोड़कर आगे बढ़ें: recur(i+1, cur)।
   • यदि words[i] के सभी वर्ण अद्वितीय हैं और cur + words[i] के सभी वर्ण अद्वितीय हैं, तो इसे शामिल करें: recur(i+1, cur + words[i])।
4. recur(0, "") कॉल करें और ans वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, words):
        ans = 0
        
        def is_unique(s):
            return len(set(s)) == len(s)
        
        def recur(i=0, cur=""):
            nonlocal ans
            if i == len(words):
                ans = max(ans, len(cur))
                return
            # वर्तमान शब्द छोड़ें
            recur(i + 1, cur)
            # वर्तमान शब्द शामिल करें यदि संभव हो
            if is_unique(words[i]) and is_unique(cur + words[i]):
                recur(i + 1, cur + words[i])
        
        recur()
        return ans

# परीक्षण
ob = Solution()
words = ["xyz", "xyw", "wab", "cde"]
print(ob.solve(words))  # आउटपुट: 9

बिटमास्क अनुकूलन

प्रत्येक शब्द को 26-बिट पूर्णांक (a-z के लिए) के रूप में दर्शाया जा सकता है। यदि शब्द में डुप्लिकेट वर्ण हैं, तो उसे छोड़ दें। फिर बैकट्रैकिंग में बिटवाइज़ AND/OR का उपयोग करके O(1) में अद्वितीयता जांचें। यह बड़े इनपुट के लिए बहुत तेज़ है।

समय जटिलता

• बैकट्रैकिंग: O(2^n × L) जहां n शब्दों की संख्या है और L औसत लंबाई है।
• बिटमास्क के साथ: O(2^n) व्यावहारिक रूप से तेज़।