【Python】隣接する同じ文字をなくすための最小削除コストを求めるアルゴリズム

問題の概要

文字列 s と整数型の配列 cost が与えられます。ここで cost[i] は、s の i 番目の文字を削除する際にかかるコストを表します。このとき、「同じ文字が隣り合わない状態」にするために必要な最小の削除コストを求めるのが目的です。

重要なポイントとして、選んだ文字はすべて同時に削除されます。そのため、ある文字を削除しても、他の文字の削除コストは変化しないという前提で計算を行います。

入力例と出力例

たとえば、入力が s = "pptpp"、cost = [2,3,4,5,2] の場合を考えてみましょう。

最初と最後の「p」をそれぞれコスト 2 ずつ(合計 4)で削除すると、文字列は "ptp" になります。この結果、同じ文字が連続して並ぶことはなくなります。したがって、出力は 4 となります。

解法のアプローチ

この問題は貪欲法(グリーディ法)で効率よく解くことができます。基本的な考え方は次のとおりです。

• 累積コスト cost_f を 0 で初期化し、走査位置 i を 1 から始めます。
• 現在の文字 cur = s[i] とそのコスト c_cost、直前の文字 prev とそのコスト p_cost を取得します。
• フラグ ind が 1 の場合は、直前の文字情報として保存しておいた prev_i・cost_i を使用します。
• 現在の文字と直前の文字が同じ場合:
  • 現在の文字のコストのほうが大きい(または等しい)なら、直前の文字を削除対象とみなし、そのコストを加算します。
  • 逆に現在の文字のコストのほうが小さいなら、現在の文字を削除対象とし、そのコストを加算して、直前の文字情報を保持したまま次へ進みます。
• 文字が異なる場合は、保持していた情報をリセットして次へ進みます。
• 最後に累積コスト cost_f を返します。

言い換えると、同じ文字が連続している区間では、コストが最大の1文字だけを残し、それ以外をすべて削除するのが最適戦略です。このアルゴリズムは文字列を一度走査するだけで済むため、計算量は O(n) と非常に効率的です。

Pythonでの実装例

以下に、上記のアプローチを実装したPythonコードを示します。

def solve(s, cost):
    cost_f = 0
    i = 1
    ind = 0

    for i in range(1, len(s)):
        cur, c_cost = s[i], cost[i]
        prev, p_cost = s[i-1], cost[i-1]
        if ind == 1:
            prev, p_cost = prev_i, cost_i

        if cur == prev:
            if c_cost >= p_cost:
                cost_f += p_cost
                prev_i, cost_i = 0, 0
                ind = 0

            if c_cost < p_cost:
                cost_f += c_cost
                ind = 1
                prev_i, cost_i = prev, p_cost

        else:
            prev_i, cost_i = 0, 0
            ind = 0
    return cost_f

s = "pptpp"
cost = [2,3,4,5,2]
print(solve(s, cost))

入力

"pptpp", [2,3,4,5,2]

出力

4

まとめ

この問題では、連続する同一文字の中から最も削除コストの高い文字を残し、それ以外を削除することで最小コストを達成できます。フラグ変数を使って「どの文字を仮想的な直前文字として保持しているか」を管理するのが実装上のポイントです。線形時間 O(n) で処理できるため、長い文字列に対しても高速に動作します。