মনে করুন আমাদের একটি স্ট্রিং s এবং আরেকটি স্ট্রিং t আছে। এবং t, s-এর একটি সাবসিকোয়েন্স। আমাদের s থেকে একটি সাবস্ট্রিং সরাতে হবে যাতে t এখনও s-এর একটি সাবসিকোয়েন্স থাকে, এবং সরানো সাবস্ট্রিংর দৈর্ঘ্য সর্বোচ্চ হবে।
উদাহরণস্বরূপ, যদি ইনপুট হয় s = "xyzxyxz", t = "yz", তবে আউটপুট হবে 4, কারণ আমরা "abca" সাবস্ট্রিংটি সরাতে পারি।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
left := একটি নতুন তালিকা, right := আরেকটি নতুন তালিকা
c1 := -1, c2 := -1, c3 := -1
j := 0
i = 0 থেকে s-এর আকার পর্যন্ত, করুন
যদি s[i] t[j]-এর সমান হয়, তবে
left-এর শেষে i যোগ করুন
j := j + 1
যদি j t-এর আকারের সমান হয়, তবে
c1 := s-এর আকার - i - 1
লুপ থেকে বের হন
j := t-এর আকার - 1
i = s-এর আকার - 1 থেকে 0 পর্যন্ত, 1 করে কমিয়ে, করুন
যদি s[i] t[j]-এর সমান হয়, তবে
right-এর 0 নম্বর পজিশনে i যোগ করুন
j := j - 1
যদি j -1-এর সমান হয়, তবে
c2 := i
লুপ থেকে বের হন
i = 0 থেকে t-এর আকার - 1 পর্যন্ত, করুন
c3 := c3 এবং (right[i + 1] - left[i] - 1)-এর সর্বোচ্চ
c1, c2 এবং c3-এর সর্বোচ্চ রিটার্ন করুন
উদাহরণ (পাইথন)
বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:
class Solution: def solve(self, s, t): left = [] right = [] c1 = -1 c2 = -1 c3 = -1 j = 0 for i in range(len(s)): if s[i] == t[j]: left.append(i) j += 1 if j == len(t): c1 = len(s) - i - 1 break j = len(t) - 1 for i in range(len(s) - 1, -1, -1): if s[i] == t[j]: right.insert(0, i) j -= 1 if j == -1: c2 = i break for i in range(len(t) - 1): c3 = max(c3, right[i + 1] - left[i] - 1) return max(c1, c2, c3) ob = Solution() s = "xyzxyxz" t = "yz" print(ob.solve(s, t))
ইনপুট
"xyzxyxz", "yz"
আউটপুট
4
