C++で連続する重複文字を削除する最小コストを求めるプログラム

小文字だけで構成された文字列 s と、非負整数のリスト nums があるとします。両者の長さは同じです。文字 s[i] を削除するにはコスト nums[i] がかかり、削除後は s[i] と nums[i] の両方が取り除かれます。このとき、連続して繰り返される文字をすべてなくすために必要な最小コストを求めるのが本問題です。

入力例と出力例

たとえば、入力が s = "xxyyx"、nums = [2, 3, 10, 4, 6] の場合を考えてみましょう。このとき出力は 6 になります。s[0]（'x'）と s[3]（'y'）を削除すると、残りの文字列は "xyx" となり連続する重複がなくなります。このときの合計コストは 2 + 4 = 6 で、これが最小となります。

解法のアプローチ：スタックを使った貪欲法

ポイントは、「同じ文字が連続している区間では、最もコストの高い文字を1つだけ残し、それ以外をすべて削除する」という貪欲な戦略を取ることです。これを実現するためにスタックを利用します。スタックには「その時点で残す候補となる文字のインデックス」だけを保持し、新しい文字がスタックトップの文字と同じ場合は、コストの低い方を削除費用として加算し、コストの高い方をスタックに残します。

アルゴリズムの手順

• インデックスを格納するスタック st を用意し、cost を 0 で初期化します。
• i を 0 から s の長さ - 1 まで順に処理します。
  • st が空でなく、かつ s[st.top()] が s[i] と等しい場合：
    • nums[st.top()] > nums[i] ならば、cost += nums[i]（現在の文字を削除）。
    • そうでなければ、cost += nums[st.top()] としてスタックトップの文字を削除し、st からポップして i をプッシュします。
  • 上記以外の場合は、単純に i を st にプッシュします。
• 最後に cost を返します。

この方法では各文字を一度ずつ処理するため、時間計算量は O(n)、空間計算量も O(n) となります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
   int solve(string s, vector<int>& nums) {
      stack<int> st;
      int cost = 0;
      for (int i = 0; i < s.size(); ++i) {
         if (st.size() && s[st.top()] == s[i]) {
            if (nums[st.top()] > nums[i]) {
               cost += nums[i];
            } else {
               cost += nums[st.top()];
               st.pop();
               st.push(i);
            }
         } else {
            st.push(i);
         }
      }
      return cost;
   }
};

int solve(string s, vector<int>& nums) {
   return (new Solution())->solve(s, nums);
}

main(){
   vector<int> v = {2, 3, 10, 4, 6};
   string s = "xxyyx";
   cout << solve(s, v);
}

実行結果

入力：

"xxyyx", {2, 3, 10, 4, 6}

出力：

6

まとめ

連続する重複文字の削除コストを最小化する問題は、スタックを用いた貪欲法で効率的に解くことができます。「各区間で最も高価な文字を1つ残す」というシンプルな発想が鍵となり、計算量 O(n) で処理できる点が大きな魅力です。