Pythonで部分文字列を削除して最大スコアを求めるプログラムの解説

問題概要

文字列 s と2つの整数値 x、y が与えられているとします。次の2種類の操作を任意の回数だけ実行できます。

• 部分文字列「ab」を検索し、存在する場合はそれを削除して x ポイントを獲得する。
• 部分文字列「ba」を検索し、存在する場合はそれを削除して y ポイントを獲得する。

これらの操作を文字列 s に適用した後、獲得できる最大ポイントを求めるのが目的です。

具体例

たとえば、入力が s = "cbbaacdeabb"、x = 4、y = 5 の場合、出力は 14 になります。その過程は以下の通りです。

1. 初期状態の文字列は「cbbaacdeabb」。まず「cbbaacde(ab)b」のように「ab」を削除して4ポイント獲得し、文字列は「cbbaacdeb」になります。
2. 次に「cb(ba)acdeb」のように「ba」を削除してさらに5ポイント獲得。現在のスコアは 4+5=9、文字列は「cbacdeb」です。
3. 続いて「c(ba)cdeb」のように再び「ba」を削除して5ポイント追加。スコアは 9+5=14、文字列は「ccdeb」となります。
4. この時点で削除できる部分文字列はもう存在しないため、最終的な答えは 14 です。

解法のアプローチ

この問題は貪欲法(グリーディ法)を用いて効率的に解くことができます。基本的な考え方は、「より高得点となるペアを優先的に削除する」というものです。具体的な手順は以下の通りです。

• a := 'a'、b := 'b' として初期化します。
• ans := 0、a_st := 0、b_st := 0 として初期化します(a_st と b_st はそれぞれ未処理の 'a' と 'b' のカウンタです)。
• y > x の場合、a と b を入れ替え、x と y も入れ替えます。これにより、常に得点の高いペア(x 点)から優先的に処理できるようになります。
• 文字列 s 内の各文字 c について、以下を繰り返します。
  • c が a と等しい場合:a_st を1増やします。
  • c が b と等しい場合:a_st が0でなければ、ans に x を加算して a_st を1減らします(高得点ペアを即座に消費)。a_st が0の場合は b_st を1増やします。
  • それ以外の文字の場合:ans に y × min(a_st, b_st) を加算し、a_st と b_st を0にリセットします(区切り文字によって残ったペアを低得点で処理します)。
• 最終的に ans + y × min(a_st, b_st) を返します。

実装例

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

def solve(s, x, y):
    a = 'a'
    b = 'b'
    ans = 0
    a_st = 0
    b_st = 0
    if y > x:
        a, b = b, a
        x, y = y, x
    for c in s:
        if c == a:
            a_st += 1
        elif c == b:
            if a_st:
                ans += x
                a_st -= 1
            else:
                b_st += 1
        else:
            ans += y * min(a_st, b_st)
            a_st = 0
            b_st = 0
    return ans + y * min(a_st, b_st)

s = "cbbaacdeabb"
x = 4
y = 5
print(solve(s, x, y))

入力

"cbbaacdeabb", 4, 5

出力

14

まとめ

このアルゴリズムは文字列を一度走査するだけで済むため、時間計算量は O(n)、空間計算量も O(1) と非常に効率的です。得点の高いペアを優先的に削除する貪欲な戦略により、常に最大スコアを達成できる点がポイントです。