C++で文字列からk個の一意な部分列を選択する最小コストを求めるプログラム

問題の概要

文字列 s と整数 k が与えられます。s の部分列(サブシーケンス)をいくつか選び、合計で k 個の一意な(重複しない)部分列を集めることを考えます。

ここで、ある部分列を選択するコストは次のように定義されます。

コスト = s の長さ − 選択した部分列の長さ

目的は、k 個の一意な部分列を選んだときの合計コストの最小値を求めることです。k 個集めることが不可能な場合は -1 を返します。なお、空文字列も有効な部分列として扱います。

たとえば、入力が s = "pqrs"、k = 4 の場合、出力は 3 になります。

解き方の考え方

コストの定義から、できるだけ長い部分列から優先的に選ぶほど合計コストを小さくできます。そのためには、「長さごとに何種類の一意な部分列が存在するか」を正確に数える必要があります。

これを効率よく求めるために動的計画法(DP)を活用します。dp[i][j] を「先頭 i 文字から作れる、長さ j の一意な部分列の個数」と定義します。同じ文字が再登場したときに、以前に数えた分を差し引くことで重複を排除するのがポイントです。

アルゴリズムの手順

• n := s の長さとする
• (n + 1) × (n + 1) の2次元配列 dp を宣言し、すべて 0 で初期化する
• 各文字が最後に現れた位置を記録するマップ last を用意する
• dp[0][0] := 1 とする(空文字列は常に1通り)
• i := 0 から n - 1 まで、i を 1 ずつ増やしながら以下を繰り返す:
  • dp[i + 1][0] := 1 とする
  • j := i + 1 から 1 まで、j を 1 ずつ減らしながら dp[i + 1][j] := dp[i][j] + dp[i][j - 1] を計算する
  • s[i] が last に登録済みの場合、j := 0 から last[s[i]] まで dp[i + 1][j + 1] -= dp[last[s[i]]][j] として重複分を差し引く
  • last[s[i]] := i と更新する
• cost := 0 とする
• i := n から 0 まで、i を 1 ずつ減らしながら(長い部分列から順に):
  • val := min(k, dp[n][i]) とする
  • cost += val × (n - i)
  • k -= dp[n][i]
  • k <= 0 になったらループを抜ける
• k <= 0 なら cost を返し、そうでなければ -1 を返す

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(string s, int k) {
    int n = s.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    unordered_map<char, int> last;
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        dp[i + 1][0] = 1;
        for (int j = (i + 1); j >= 1; j--) {
            dp[i + 1][j] = dp[i][j] + dp[i][j - 1];
        }
        if (last.find(s[i]) != last.end()) {
            for (int j = 0; j <= last[s[i]]; j++) {
                dp[i + 1][j + 1] -= dp[last[s[i]]][j];
            }
        }
        last[s[i]] = i;
    }
    int cost = 0;
    for (int i = n; i >= 0; i--) {
        int val = min(k, dp[n][i]);
        cost += (val * (n - i));
        k -= dp[n][i];
        if (k <= 0) {
            break;
        }
    }
    if (k <= 0) {
        return cost;
    }
    return -1;
}
int main(){
    cout << solve("pqrs",4) << endl;
    return 0;
}

入力

"pqrs", 4

出力

3

出力の解説

s = "pqrs" の場合、長さ 4 の一意な部分列は "pqrs" のみで、そのコストは 0 です。残りの 3 個は長さ 3 の部分列("pqr"、"pqs"、"qrs" など)から選べます。それぞれのコストは 4 − 3 = 1 なので、合計コストは 0 + 1 × 3 = 3 となります。

計算量について

DPテーブルの構築と重複除去の処理を合わせて、時間計算量は O(n²)(n は文字列の長さ)、空間計算量も O(n²) となります。なお、一意な部分列の総数は文字数に対して指数的に増大するため、実際の応用では大きな整数型や剰余演算を組み合わせる工夫が必要になる点にも注意しましょう。