Pythonで同じ文字からなる両端を削除した後の文字列の最小長を求めるプログラム

問題概要

「a」「b」「c」の3種類の文字のみで構成された文字列 s が与えられます。この文字列に対して、以下のルールに従う操作を任意の回数(0回でも可)実行することを考えます。

• すべての文字が同一である、空でない接頭辞(先頭部分)を選ぶ
• すべての文字が同一である、空でない接尾辞(末尾部分)を選ぶ
• 接頭辞と接尾辞は互いに重なっていてはならない
• 接頭辞と接尾辞を構成する文字は同じでなければならない
• 選んだ接頭辞と接尾辞の両方を文字列から削除する

これらの操作を好きなだけ繰り返した後に残る文字列 s の最小の長さを求めるのが目的です。

例えば、入力が s = "aabccabba" の場合、出力は 3 になります。まず接頭辞 "aa" と接尾辞 "a" を選んで削除すると "bccabb" となり、続けて接頭辞 "b" と接尾辞 "bb" を削除すると "cca" が残ります。この長さはちょうど 3 です。

解法のアプローチ

この問題は、deque(両端キュー)を活用すると効率的に解くことができます。貪欲法の考え方で、先頭と末尾の文字が一致する限り、その文字ブロックを両側から削り落としていくイメージです。具体的な手順は以下の通りです。

• 文字列 s を deque に変換する
• s のサイズが 1 より大きく、かつ先頭要素と末尾要素が一致している間、以下を繰り返す:
  • chk として先頭の文字を記録する
  • 先頭の文字が chk と等しい限り、左端の要素を削除し続ける
  • 末尾の文字が chk と等しい限り、右端の要素を削除し続ける
• 最終的に残った s のサイズを返す

このアルゴリズムでは、各文字は高々1回ずつ削除されるため、計算量は O(n) となり、非常に効率的です。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

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

まとめ

本記事では、「a・b・c」のみで構成される文字列から、同じ文字からなる接頭辞と接尾辞をペアで削除していく操作を繰り返し、最終的な最小長を求める問題を扱いました。deque を使うことで、先頭と末尾からの効率的な削除が可能になり、線形時間 O(n) で解ける点がポイントです。同様の「両端から詰めていく」パターンは、他の文字列操作系の問題にも応用できるので、ぜひ覚えておきましょう。