পাইথনে অনন্য ক্যারেক্টার সম্বলিত স্ট্রিং কনক্যাটেনেট করে সর্বাধিক দৈর্ঘ্য বের করার প্রোগ্রাম

ধরা যাক words নামক একটি স্ট্রিং লিস্ট রয়েছে। আমাদের words-এর একটি সাবসিকোয়েন্স কনক্যাটেনেট করে একটি স্ট্রিং তৈরি করতে হবে যাতে প্রতিটি অক্ষর অনন্য (unique) থাকে। তারপর সেই সবচেয়ে বড় কনক্যাটেনেট করা স্ট্রিং-এর দৈর্ঘ্য বের করতে হবে।

উদাহরণ

ইনপুট: words = ["xyz", "xyw", "wab", "cde"]

আউটপুট: 9

ব্যাখ্যা: যেহেতু শব্দগুলিতে ডুপ্লিকেট ক্যারেক্টার রয়েছে, তাই কোনো শব্দ বেছে নেওয়া সম্ভব নয়। তবে সঠিক উত্তর ৯ হওয়া উচিত কারণ "xyz" + "wab" + "cde" = "xyzwabcde" (দৈর্ঘ্য ৯) যেখানে সব ক্যারেক্টার অনন্য।

সমাধানের ধাপসমূহ

1. ans := 0
2. recur() ফাংশন সংজ্ঞায়িত করুন যা i:=0 এবং cur:="" (খালি স্ট্রিং) নেয়
3. যদি i == len(words) হয়, তবে:
   • ans := max(ans, len(cur))
   • ফেরত যান
4. recur(i + 1, cur) কল করুন (বর্তমান শব্দ বাদ দিয়ে)
5. যদি words[i]-এর সব ক্যারেক্টার অনন্য হয় এবং cur + words[i]-এর সব ক্যারেক্টার অনন্য হয়, তবে:
   • recur(i + 1, cur + words[i]) কল করুন (বর্তমান শব্দ যোগ করে)
6. মূল মেথড থেকে recur() কল করুন
7. ans ফেরত দিন

পাইথন ইমপ্লিমেন্টেশন

class Solution:
    def solve(self, words):
        ans = 0
        def is_all_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_all_unique(words[i]) and is_all_unique(cur + words[i]):
                recur(i + 1, cur + words[i])
        recur()
        return ans

ob = Solution()
words = ["xyz", "xyw", "wab", "cde"]
print(ob.solve(words))

ইনপুট

["xyz", "xyw", "wab", "cde"]

আউটপুট

9