পাইথনে জোড় সংখ্যক স্বরবর্ণ ধারণকারী সর্বোচ্চ দৈর্ঘ্যের সাবস্ট্রিং খুঁজে বের করার প্রোগ্রাম

একটি ছোট হাতের স্ট্রিং s দেওয়া আছে। আমাদের এমন সবচেয়ে বড় সাবস্ট্রিং খুঁজে বের করতে হবে যাতে সেটিতে উপস্থিত প্রতিটি স্বরবর্ণ (a, e, i, o, u) জোড় সংখ্যকবার উপস্থিত থাকে।

উদাহরণস্বরূপ, s = "anewcoffeepot" হলে আউটপুট হবে ১০, কারণ "wcoffeepot" সাবস্ট্রিং-এ 'o' এবং 'e'—এই দুটি স্বরবর্ণই আছে এবং প্রতিটিই দুবার করে আসেছে।

সমাধানের পদ্ধতি (বিটমাস্ক + প্রিফিক্স ম্যাপ)

স্বরবর্ণগুলোর জন্য একটি ম্যাপ বানান: {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}।
prefix = {0: -1} ইনিশিয়ালাইজ করুন (মাস্ক ০-এর প্রথম ইনডেক্স -১)۔
mask = 0, res = 0।
স্ট্রিং-এ প্রতিটি ক্যারেক্টার i তে:
- যদি ক্যারেক্টারটি স্বরবর্ণ হয়, তবে mask ^= 1 << vowels[char] করে সংশ্লিষ্ট বিট টগল করুন।
- যদি এই mask প্রথমবার দেখা যায়, তবে prefix[mask] = i সংরক্ষণ করুন।
- অন্যথায়, একই মাস্ক আগে দেখা গেছে অর্থাৎ দুটি প্রিফিক্সের মধ্যে স্বরবর্ণের প্যারিটি একই → সাবস্ট্রিং-এ সব স্বরবর্ণ জোড় বার আছে। তখন res = max(res, i - prefix[mask]) আপডেট করুন।
res রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, s):
        vowels = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
        prefix = {0: -1}
        mask = 0
        n = len(s)
        res = 0
        for i in range(n):
            if s[i] in vowels:
                mask ^= 1 << vowels[s[i]]
            if mask not in prefix:
                prefix[mask] = i
            else:
                res = max(res, i - prefix[mask])
        return res

ob = Solution()
s = "anewcoffeepot"
print(ob.solve(s))

ইনপুট

"anewcoffeepot"