Pythonで大文字・小文字の隣接ペアを削除して「良い文字列」を作るプログラム

問題の概要

英小文字と英大文字で構成された文字列 s が与えられます。次の両方の条件を満たす隣接する2文字 s[i] と s[i + 1] が一切含まれていない文字列を「良い文字列（good string）」と定義します。

• 0 <= i <= len(s) - 2
• s[i] が小文字で、s[i + 1] が同じ英字の大文字である（またはその逆）

文字列を良い文字列へ変換するには、文字列を「悪い」状態にしている隣接する2文字を選んで削除します。この操作を、文字列が良くなるまで繰り返します（空文字列も良い文字列とみなします）。そして、最終的に得られる文字列を求めます。

入力例

たとえば s = "popPpulaBbr" が入力された場合、出力は "popular" になります。これは、まず "pP" を削除し、続いて "Bb" を削除すると良い文字列になるためです。

解法のアプローチ

この問題は、スタックのように使えるリストを用意して、文字列を先頭から順に処理することで効率的に解けます。手順は以下のとおりです。

• 結果を格納するための新しいリスト res を用意する
• 文字列 s の各文字 ch について次を繰り返す
  • res が空でなく、末尾の要素と ch が大文字・小文字の違いを無視して同じ文字であれば、res の末尾の要素を削除する
  • それ以外の場合は、ch を res の末尾に追加する
• 最後に res 内の要素をすべて連結して返す

この方法では各文字を一度ずつ処理するだけでよいため、計算量は文字数に比例する O(n) に抑えられ、非常に効率的です。

Pythonでの実装例

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

def solve(s):
    res = []
    for ch in s:
        if res and res[-1] != ch and res[-1].lower() == ch.lower():
            res.pop()
        else:
            res.append(ch)
    return ''.join(res)

s = "popPpulaBbr"
print(solve(s))

入力

"popPpulaBbr"

出力

popular

まとめ

隣接する大文字・小文字のペアを削除して文字列を整える問題は、スタックの考え方を使うと簡潔に解決できます。文字を先頭から走査し、直前の文字と大文字小文字を区別せずに比較して一致すれば削除、そうでなければ追加——このシンプルな操作の繰り返しが答えにつながります。計算量は O(n) であり、長い文字列に対しても高速に動作する点が魅力です。