C++プログラム：良い文字列を作るために削除すべき文字数の求め方

問題概要

文字列 S が与えられます。S には「x」と「a」の2種類の文字が含まれています。いくつかの文字を取り除いた後に残る文字列が「良い文字列」となるようにするとき、残せる文字列の長さの最大値を求めます。ここで「良い文字列」とは、文字列全体の長さの半分を厳密に超える数の「a」が含まれている文字列のことです。

たとえば、入力が S = "xaxxxxa" の場合、出力は 3 になります。「x」を4つ削除すると文字列は "xaa" となり、これは長さ 3 の良い文字列だからです。

解法のアプローチ

この問題は、次の手順で効率よく解くことができます。

x := 2 ×（S に含まれる 'a' の個数）− 1
n := 文字列 S の長さ
return min(n, x)

この式の考え方は以下の通りです。「a」の個数を cnt とすると、良い文字列では「a」が全体の半分より厳密に多く含まれる必要があるため、cnt 個の「a」を使って作れる良い文字列の長さは最大でも 2 × cnt − 1 となります。また、削除によって文字列が元の長さ n より長くなることはないため、答えは n と 2 × cnt − 1 の小さい方になります。

実装例

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

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

int solve(string S) {
    int x = 2 * count(S.begin(), S.end(), 'a') - 1;
    int n = S.size();
    return min(n, x);
}

int main() {
    string S = "xaxxxxa";
    cout << solve(S) << endl;
}

入力

"xaxxxxa"

出力

3

まとめ

このアルゴリズムは、文字列を一度走査して「a」の個数を数えるだけなので、時間計算量は O(n)、追加のメモリは O(1) で済みます。非常にシンプルながら、貪欲的な考え方で最適解が得られる好例といえるでしょう。