여전히 제거할 수 있는 부분 시퀀스의 길이를 찾는 프로그램 t는 Python에서 s의 부분 시퀀스입니다.

<시간/>

문자열 s와 다른 문자열 t가 있다고 가정합니다. 그리고 t는 s의 부분수열입니다. t가 여전히 s의 부분 시퀀스가 되도록 s에서 제거할 수 있는 부분 문자열의 최대 길이를 찾아야 합니다.

따라서 입력이 s ="xyzxyxz" t ="yz"와 같으면 하위 문자열 "abca"를 제거할 수 있으므로 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

왼쪽 :=새 목록, 오른쪽 :=새 목록도
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]와 같으면
  - i를 위치 0의 오른쪽에 삽입
  - j :=j - 1
- j가 -1과 같으면
  - c2 :=나는
  - 루프에서 나오다
범위 0에서 t - 1까지의 i에 대해 수행
- c3 :=c3의 최대값 및 (오른쪽[i + 1] - 왼쪽[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"