在Python中查找删除相似末尾后字符串的最小长度

假设我们有一个仅包含三个字符’a’、’b’和’c’的字符串s。我们将对该字符串应用以下算法任意次数−

从s中选择一个非空前缀，其中前缀中的所有字符都相同。
从s中选择一个非空后缀，其中后缀中的所有字符都相同。
前缀和后缀是不相交的。
前缀和后缀中的字符必须相同。
从s中删除前缀和后缀。

最后，我们必须找到在执行上述操作任意次数（可能为零次）后的s的最小长度。

因此，如果输入是 s = “aabccabba”，则输出将为 3，因为我们首先可以选择前缀 = “aa” 和后缀 =” a”，因此删除后的字符串是 “bccabb”，然后选择前缀 =” b “和后缀”bb”，因此删除后的字符串是 “cca”，长度为3。

要解决此问题，我们将遵循以下步骤−

s:=用s创建一个队列
while s的大小> 1并且s [0]是s的最后一个元素，do
- chk:=s [0]
- while s和s[0]相同，do
  - 删除左侧元素s
- while 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))