Pythonで文字列内のすべてのAをBより前に配置するために必要な最小削除文字数を求めるプログラム

問題概要

文字「A」と「B」の2種類のみで構成される文字列 s が与えられたとします。このとき、すべての「A」がすべての「B」よりも前に並ぶようにするために、文字列 s から削除する必要がある文字の最小数を求めるのが目的です。

例えば、入力が S = "AABAABB" の場合、出力は 1 になります。最後の「A」を1つ削除すれば "AABBB" となり、すべての A が B より前に配置されるためです。

解法のアプローチ

この問題は、文字列を左から右へ一度走査しながら、各区切り位置において「削除が必要な文字数」を計算していくことで効率的に解けます。具体的には、次の手順に従います。

• a_right := 文字列 s 内の「A」の出現回数(まだ走査していない右側の A の数)

• b_left := 0(すでに走査した左側の B の数)

• ans := a_right(初期値)

• 文字列 s の各インデックス i と文字 c に対して、以下を繰り返します。

  • c が「A」と同じ場合:a_right を 1 減らします

  • それ以外の場合:b_left を 1 増やします

  • ans := ans と (a_right + b_left) のうち小さい方で更新します

• 最後に ans を返します

このアプローチのポイントは、文字列をある位置で区切ったとき、境界より左側にある「B」と右側にある「A」をすべて削除すれば、残りの文字列は必ず「A…AB…B」の形になるという点です。したがって、各区切り位置における「左側の B の数 + 右側の A の数」を全て調べ、その最小値が答えとなります。

実装例

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

例

class Solution:
    def solve(self, s):
        a_right = s.count("A")
        b_left = 0

        ans = a_right
        for i, c in enumerate(s):
            if c == "A":
                a_right -= 1
            else:
                b_left += 1
            ans = min(ans, a_right + b_left)
        return ans

ob = Solution()
S = "AABAABB"
print(ob.solve(S))

入力

"AABAABB"

出力

1

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、使用する追加メモリは定数のみなので空間計算量は O(1) となります。文字列の長さが大きくなっても効率的に動作する、非常にシンプルかつ実用的な解法です。