পাইথনে স্ট্রিং ক্যারেক্টার দিয়ে kটি প্যালিনড্রোম বানানো সম্ভব কিনা চেক করা

সমস্যা বিবরণ

একটি স্ট্রিং s এবং সংখ্যা k দেওয়া আছে। স্ট্রিংয়ের সব ক্যারেক্টার ব্যবহার করে ঠিক kটি প্যালিনড্রোম বানানো সম্ভব কিনা চেক করতে হবে।

উদাহরণ

Input:  s = "amledavmel", k = 2
Output: True
ব্যাখ্যা: "level" এবং "madam" বানানো সম্ভব

কী অভিজ্ঞতা (Key Insight)

একটি প্যালিনড্রোমে শুধু একটি অড্ড (বিষম) ফ্রিকোয়েন্সি वाला ক্যারেক্টার থাকতে পারে (মাঝপথে)। অতএব, kটি প্যালিনড্রোম বানাতে হলে স্ট্রিংয়ে অড্ড ফ্রিকোয়েন্সি वाले ক্যারেক্টার সংখ্যা ≤ k হতে হবে।

অ্যালগরিদম

1. প্রতিটি ক্যারেক্টার ফ্রিকোয়েন্সি গণনা করুন (Counter)
2. অড্ড ফ্রিকোয়েন্সি वाले ক্যারেক্টার কাউন্ট করুন (cnt)
3. যদি cnt > k হলে → False
4. অন্যথায় → True

পাইথন কোড

from collections import Counter

class Solution:
    def solve(self, s, k):
        freq = Counter(s)
        odd_count = sum(1 for v in freq.values() if v % 2 == 1)
        
        if odd_count > k:
            return False
        return True

ob = Solution()
s = "amledavmel"
k = 2
print(ob.solve(s, k))  # True

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n) — n = স্ট্রিং দৈর্ঘ্য
• স্থান জটিলতা: O(1) — ক্যারেক্টার সেট সিমিত (ASCII: 256, Unicode: বেশি কিন্তু বাউন্ডেড)

এজ কেস

• k > len(s) → অসম্ভব (প্রতিটি প্যালিনড্রোমে কমপক্ষে ১ ক্যারেক্টার লাগে)
• k == len(s) → সবসময় True (প্রতিটি ক্যারেক্টার আলাদা প্যালিনড্রোম)
• খালি স্ট্রিং → k == 0 হলে True

উপসংহার

• প্যালিনড্রোম কন্সট্রাকশনের কী শর্ত: অড্ড ফ্রিকোয়েন্সি ≤ ১
• kটি প্যালিনড্রোমের জন্য অড্ড ফ্রিকোয়েন্সি ≤ k
• O(n) সময়ে সমাধান সম্ভব