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

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

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

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

n := 0
pos_map := {0: len(s)} ম্যাপ
max_len := 1
i = s-এর সাইজ - ১ থেকে ০ পর্যন্ত (কমাতে ১)
- n := n XOR (1 << int(s[i]))
- যদি n pos_map-এ থাকে, তবে
  - max_len := max(max_len, pos_map[n] - i)
- j = 0 থেকে ৯ পর্যন্ত
  - m := n XOR (1 << j)
  - যদি m pos_map-এ থাকে, তবে
    - max_len := max(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"