まだ削除できるサブシーケンスの長さを見つけるプログラムtはPythonのsのサブシーケンスです

文字列sと別の文字列tがあるとします。そして、tはsのサブシーケンスです。 tがsのサブシーケンスであるように、sから削除できるサブストリングの最大長を見つける必要があります。

したがって、入力がs ="xyzxyxz" t ="yz"の場合、サブストリング "abca"

これを解決するには、次の手順に従います-

• 左：=新しいリスト、右：=また新しいリスト

• c1：=-1、c2：=-1、c3：=-1

• j：=0

• 0からsのサイズの範囲のiの場合、実行します

  • s[i]がt[j]と同じ場合、

    • 左端にiを挿入

    • j：=j + 1

  • jがtのサイズと同じである場合、

    • c1：=sのサイズ--i-1

    • ループから出てきます

• j：=tのサイズ-1

• s-1から0の範囲サイズのiの場合、1ずつ減らします。

  • s[i]がt[j]と同じ場合、

    • 位置0の右側にiを挿入します

    • j：=j-1

  • jが-1と同じ場合、

    • c2：=i

    • ループから出てきます

• 範囲0からt-1のサイズのiの場合、実行

  • c3：=最大c3および（right [i + 1] --left [i] -1）

• c1、c2、c3の最大値を返す

例（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