Python中查找可以删除的子序列的长度t是s的子序列

假设我们有一个字符串s和另一个字符串t。t是s的子序列。我们必须找到可以从s中删除的子字符串的最大长度，以便t仍然是s的子序列。

因此，如果输入类似于s =“ xyzxyxz” t =“ yz”，则输出将为4，因为我们可以删除子字符串“ abca”

范例(Python)

让我们看下面的实现以更好地理解-

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