মনে করুন আমাদের কাছে দুটি স্ট্রিং, s এবং t আছে। আমরা নিচের পদ্ধতিতে একটি স্ট্রিং বানাতে চাই −
s থেকে কিছু নন-এম্পটি সাবসিকোয়েন্স sub1 সিলেক্ট করুন।
t থেকে কিছু নন-এম্পটি সাবসিকোয়েন্স sub2 সিলেক্ট করুন।
sub1 এবং sub2 কনক্যাটেনেট করুন, স্ট্রিং বানান।
আমাদের উপরে বর্ণিত পদ্ধতিতে বানানো সবচেয়ে লম্বা প্যালিনড্রোমের দৈর্ঘ্য বের করতে হবে। যদি কোনো প্যালিনড্রোম বানানো না যায়, তবে 0 রিটার্ন করুন।
সুতরাং, যদি ইনপুট হয় s = "hillrace" t = "cargame", তবে আউটপুট হবে 7 কারণ আমরা s থেকে "race" এবং t থেকে "car" নিতে পারি, তাই "racecar" হলো দৈর্ঘ্য ৭ এর প্যালিনড্রোম।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
n := s-এর আকার, m := t-এর আকার
word := s + t
dp := (n+m) x (n+m) আকারের একটি ২D অ্যারে 0 দিয়ে পূরণ
i = (n + m - 1) থেকে 0 পর্যন্ত, ১ কমানো করে, করুন
j = i থেকে n + m - 1 পর্যন্ত, করুন
যদি i == j হয়, তবে
dp[i, j] := 1
অন্যথায় যখন word[i] == word[j] হয়, তবে
dp[i, j] := 2 + dp[i + 1, j - 1]
অন্যথায়,
dp[i, j] = dp[i + 1, j] এবং dp[i, j - 1] এর মধ্যে সর্বোচ্চ
ans := 0
i = 0 থেকে n-1 পর্যন্ত জন্য, করুন
j = m-1 থেকে -1 পর্যন্ত, ১ কমানো করে, করুন
যদি s[i] == t[j] হয়, তবে
ans = ans এবং dp[i, n + j] এর মধ্যে সর্বোচ্চ
ans রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন
def solve(s, t):
n, m = len(s), len(t)
word = s + t
dp = [[0] * (n + m) for _ in range(n + m)]
for i in range(n + m - 1, -1, -1):
for j in range(i, n + m):
if i == j:
dp[i][j] = 1
elif word[i] == word[j]:
dp[i][j] = 2 + dp[i + 1][j - 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
ans = 0
for i in range(n):
for j in range(m - 1, -1, -1):
if s[i] == t[j]:
ans = max(ans, dp[i][n + j])
return ans
s = "hillrace"
t = "cargame"
print(solve(s, t))
ইনপুট
[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]
আউটপুট
7
