Python দিয়ে সর্বোচ্চ দৈর্ঘ্যের প্যালিনড্রোমিক সাবসিকোয়েন্স বের করার প্রোগ্রাম

মান লাগিয়ে, আমাদের একটি স্ট্রিং দেওয়া আছে। আমাদের একটি প্যালিনড্রোমিক সাবসিকোয়েন্স বের করতে হবে যা জোড় দৈর্ঘ্যের এবং মাঝপথ ছাড়া কোনো দুটি আঞ্চলিক ক্যারেক্টার একই নয়। আমাদের এই ধরনের সাবস্ট্রিংয়ের দৈর্ঘ্য রিটার্ন করতে হবে।

যেমন, ইনপুট s = 'efeffe' হলে, আউটপুট হবে 4।

আউটপুট 4 কারণ একমাত্র জোড় দৈর্ঘ্যের প্যালিনড্রোমিক সাবসিকোয়েন্স হল 'effe' যার দৈর্ঘ্য 4।

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

• n := s-এর আকার
• dp := একটি n x n 2D অ্যারে যেখানে প্রতিটি আইটেম একটি পেয়ার (0, ব্ল্যাঙ্ক স্ট্রিং) আকারে
• i = n-1 থেকে -1 পর্যন্ত ১ কমানো হয়ে লুপ চালান:
  • j = i+1 থেকে n পর্যন্ত লুপ চালান:
    • যদি s[i] == s[j] এবং dp[i+1][j-1] এর স্ট্রিং s[i] নয়, তবে:
      • dp[i][j] := (dp[i+1][j-1][0] + 2, s[i]) পেয়ার বানান
    • অন্যথায়:
      • dp[i][j] := (dp[i+1][j], dp[i][j-1], dp[i+1][j-1]) মধ্যে যেটির প্রথম এলিমেন্ট সর্বোচ্চ সেটি নির্বাচন করুন
  • dp[0][n-1]-এ সংরক্ষিত পেয়ারের প্রথম এলিমেন্ট রিটার্ন করুন

  বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:

  উদাহরণ

  def solve(s):
      n = len(s)
      dp = [[(0, '')]*n for _ in range(n)]
      for i in range(n-1, -1, -1):
          for j in range(i+1, n):
              if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
                  dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
              else:
                  dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
      return dp[0][n-1][0]
  print(solve('efeffe'))

  ইনপুট

  'efeffe'

  আউটপুট

  4