C++で文字列から部分列「abc」を削除できる最大回数を求める方法

問題の概要

この課題では、与えられた文字列の中から特定の部分列（サブシーケンス）を何回取り除けるか、その最大回数を求めます。具体的には、文字列 s が与えられたとき、その中から部分列 「abc」 を最大で何個削除できるかを計算します。

まず、具体例を使って問題を理解しましょう。

入力例 1

s = "dnabcxy"

出力例 1

1

解説： 文字列「dnabcxy」には「abc」という部分列が1つしか含まれていないため、出力は 1 となります。

入力例 2

s = "zcabcxabc"

出力例 2

2

解説： 「zcabcxabc」には「abc」が2箇所に含まれているため、2回削除できます。

アルゴリズムの考え方

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。文字列を先頭から一度だけ走査し、「a」「b」「c」を順番に対応付けていくというシンプルな発想です。

• Max() 関数内で、int 型の変数 i、a、ab、abc をすべて 0 で初期化します。
• i = 0 から i < s.length() の範囲でループを回します。
• ループ内で s[i] == 'a' であるかを判定し、真であれば変数 a をインクリメントします（まだペアになっていない「a」の数）。
• s[i] == 'b' の場合は、さらに a > 0 かどうかを確認します。両方の条件が成立すれば、a をデクリメントして ab をインクリメントします（「a」と「b」がペアになったことを意味します）。
• s[i] == 'c' の場合は、さらに ab > 0 かどうかを確認します。両方の条件が成立すれば、ab をデクリメントして abc をインクリメントします（「abc」が1組完成したことになります）。
• ループ終了後、abc の値を返します。これが削除可能な「abc」の最大回数です。

各文字を一度だけ走査するため、時間計算量は O(n)、使用する変数は固定の4つだけなので空間計算量は O(1) となり、非常に効率的なアルゴリズムです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int Max(string s){
    int i=0, a=0, ab=0, abc=0;
    for (i = 0; i < s.length(); i++){
        if (s[i] == 'a'){
            a++;
        }
        else if (s[i] == 'b'){
            if (a > 0){
                a--;
                ab++;
            }
        }
        else if (s[i] == 'c'){
            if (ab > 0){
                ab--;
                abc++;
            }
        }
    }
    return abc;
}
//main関数
int main(){
    string s = "zcabcxabc";
    cout << Max(s);
    return 0;
}

出力結果

2

まとめ

このアルゴリズムのポイントは、文字を左から右へ走査しながら「a → ab → abc」という段階的なカウンタで状態を管理することです。「b」が出現したときに未使用の「a」が存在しなければその「b」は捨てられ、「c」が出現したときに未使用の「ab」がなければその「c」も捨てられます。この貪欲な対応付けにより、常に部分列「abc」の最大削除回数が得られることが保証されます。