Python에서 유사한 끝을 삭제한 후 문자열의 최소 길이를 찾는 프로그램

<시간/>

세 개의 문자 'a', 'b', 'c'만 있는 문자열 s가 있다고 가정합니다. 문자열에 다음 알고리즘을 여러 번 적용합니다 -

접두사의 모든 문자가 동일한 s에서 비어 있지 않은 접두사를 선택하십시오.
접미사의 모든 문자가 동일한 s에서 비어 있지 않은 접미사를 선택하십시오.
접두사와 접미사가 분리되어 있습니다.
접두사와 접미사의 문자가 같아야 합니다.
s에서 접두사와 접미사를 모두 제거하십시오.

마지막으로 위의 작업을 여러 번(0번도 가능) 수행한 후 최소 길이 s를 찾아야 합니다.

따라서 입력이 s ="aabccabba"와 같으면 출력은 처음에 접두사 ="aa" 및 접미사 ="a"를 선택할 수 있으므로 제거 후 문자열이 "bccabb"가 되도록 3이 됩니다. 접두사 ="b" 및 접미사 "bb"를 선택하므로 제거 후 문자열은 길이가 3인 "cca"입니다.

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

s :=s로 큐 만들기
크기가 s> 1이고 s[0]이 s의 마지막 요소인 동안 수행
- chk :=s[0]
- s와 s[0]이 같을 때
  - s
    에서 왼쪽 요소 삭제
- s가 비어 있지 않고 s의 마지막 요소가 chk와 동일한 동안 do
  - s
    에서 마지막 요소 삭제
s
의 반환 크기

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from collections import deque
def solve(s):
   s = deque(s)
   while len(s) > 1 and s[0] == s[-1]:
      chk = s[0]
      while s and s[0] == chk:
         s.popleft()
      while s and s[-1] == chk:
         s.pop()
   return len(s)

s = "aabccabba"
print(solve(s))

입력

"aabccabba"