পাইথনে স্পেশাল-ইকুিভ্যালেন্ট স্ট্রিং গ্রুপ

মান লেই একটি স্ট্রিং অ্যারে A আছে। S-এ একটি মুভ হলো S-এর যেকোনো দুটি ইভেন ইন্ডেক্সড ক্যারেক্টার সওয়াপ করা, অথবা যেকোনো দুটি অড ইন্ডেক্সড ক্যারেক্টার সওয়াপ করা।

এখন, দুটি স্ট্রিং S এবং T স্পেশাল-ইকুিভ্যালেন্ট যদি S-এ যেকোনো সংখ্যক মুভ করার পর S == T হয়। যেমন, S = "zzxy" এবং T = "xyzz" স্পেশাল-ইকুিভ্যালেন্ট কারণ "zzxy" থেকে "xzzy" (S[0] এবং S[2] সওয়াপ), তারপর "xyzz" (S[1] এবং S[3] সওয়াপ) করতে পারি।

এখন, A-র থেকে স্পেশাল-ইকুিভ্যালেন্ট স্ট্রিং গ্রুপ হলো A-এর একটি নন-ইম্পটি সাবসেট যাতে −

গ্রুপের প্রতিটি স্ট্রিং জোড়া স্পেশাল ইকুিভ্যালেন্ট, এবং গ্রুপটি সর্বাধিক সাইজের (অর্থাৎ এমন কোনো স্ট্রিং S গ্রুপে নেই যেটা গ্রুপের সব স্ট্রিংসহ স্পেশাল ইকুিভ্যালেন্ট)। আমাদের A-র থেকে স্পেশাল-ইকুিভ্যালেন্ট স্ট্রিং গ্রুপের সংখ্যা বের করতে হবে।

সেজন্য, যদি ইনপুট হয় ["abcd","cdab","cbad","xyzz","zzxy","zzyx"], তবে আউটপুট হবে ৩, কারণ একটি গ্রুপ ["abcd", "cdab", "cbad"], যেহেতু সব পেয়ারওয়াইজ স্পেশাল ইকুিভ্যালেন্ট, এবং অন্য স্ট্রিংগুলো এই গ্রুপের সব স্ট্রিংসহ পেয়ারওয়াইজ স্পেশাল ইকুিভ্যালেন্ট নয়। আরো দুটি গ্রুপ আছে: ["xyzz", "zzxy"] এবং ["zzyx"]।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব −

codes := একটি নতুন সেট
প্রতিটি word A-তে,
- code := ইভেন পজিশন ইন্ডেক্সের স্ট্রিং সর্ট করা + অড পজিশন ইন্ডেক্সের স্ট্রিং সর্ট করা, দুটো কনক্যাটেনেট
- code codes-এ অ্যাড
codes-এর সাইজ রিটার্ন

বেস্টার বোঝার জন্য নিচের ইম্প্লিমেন্টেশন দেখুন −

উদাহরণ

class Solution:
    def numSpecialEquivGroups(self, A):
        codes = set()
        for word in A:
            code = ''.join(sorted(word[::2])) + ''.join(sorted(word[1::2]))
            codes.add(code)
        return len(codes)

ob = Solution()
print(ob.numSpecialEquivGroups(["abcd","cdab","cbad","xyzz","zzxy","zzyx"]))

ইনপুট

["abcd","cdab","cbad","xyzz","zzxy","zzyx"]