পাইথনে দীর্ঘতম দুর্দান্ত সাবস্ট্রিং খুঁজে পাওয়ার জন্য প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যাসূচক স্ট্রিং s আছে। আমরা জানি যে একটি দুর্দান্ত সাবস্ট্রিং হল s-এর একটি অ-খালি সাবস্ট্রিং যাতে আমরা এটিকে প্যালিনড্রোম করার জন্য যে কোনও সংখ্যক অদলবদল করতে পারি। আমাদের s এর সর্বোচ্চ দৈর্ঘ্যের দুর্দান্ত সাবস্ট্রিং এর দৈর্ঘ্য খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি s ="4353526" এর মত হয়, তাহলে আউটপুট হবে 5 কারণ "35352" হল দীর্ঘতম দুর্দান্ত সাবস্ট্রিং। আমরা "35253" প্যালিনড্রোম তৈরি করতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=0
pos_map :=একটি মানচিত্র যেখানে একটি কী 0 এবং সংশ্লিষ্ট মানটি s এর আকার
max_len :=1
i এর জন্য s - 1 থেকে 0 এর পরিসরে, 1 দ্বারা হ্রাস করুন, করুন
- n :=n XOR (2^s[i])
- যদি pos_map-এ n উপস্থিত থাকে, তাহলে
  - max_len :=সর্বাধিক max_len এবং pos_map[n]-i
- 0 থেকে 9 রেঞ্জে j এর জন্য, করুন
  - m :=n XOR 2^j
  - যদি m pos_map-এ থাকে, তাহলে
    - max_len :=সর্বাধিক max_len এবং pos_map[m]-i
- n যদি pos_map-এ না থাকে, তাহলে
  - pos_map[n] :=i
রিটার্ন max_len

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

def solve(s):
   n = 0
   pos_map = {0:len(s)}

   max_len = 1

   for i in range(len(s)-1, -1, -1):
      n = n ^ (1 << int(s[i]))

      if n in pos_map:
         max_len = max(max_len, pos_map[n]-i)

      for j in range(10):
         m = n ^ (1 << j)
         if m in pos_map:
            max_len = max(max_len, pos_map[m]-i)

      if n not in pos_map:
         pos_map[n] = i

   return max_len

s = "4353526"
print(solve(s))

ইনপুট

"4353526"