Pythonで同様の端を削除した後に文字列の最小長を見つけるプログラム

'a'、'b'、および'c'の3文字のみの文字列sがあるとします。次のアルゴリズムを文字列に何度でも適用します-

• プレフィックス内のすべての文字が同じであるsから空でないプレフィックスを選択します。

• 接尾辞のすべての文字が同じであるsから空でない接尾辞を選択します。

• 接頭辞と接尾辞は互いに素です。

• プレフィックスとサフィックスの文字は同じである必要があります。

• プレフィックスとサフィックスの両方をsから削除します。

最後に、上記の操作を何度でも（場合によってはゼロ回）実行した後、sの最小長を見つける必要があります。

したがって、入力がs ="aabccabba"の場合、最初はプレフィックス="aa"とサフィックス="a"を選択できるため、出力は3になり、削除後の文字列は"bccabb"になります。プレフィックス="b"とサフィックス"bb"を選択すると、削除後の文字列は "cca"になり、長さは3になります。

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

• s：=s

  でキューを作成します

• s>1のサイズでs[0]がsの最後の要素である場合、実行

  • chk：=s [0]

  • sとs[0]は同じですが、実行してください

    • sから左の要素を削除します

  • sは空ではなく、sの最後の要素はchkと同じですが、実行してください

    • 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"

出力

3