ARC 154

Table of Contents

B - New Place

https://atcoder.jp/contests/arc154/tasks/arc154_b

$S$ の $i$ 文字目、$T$ の $j$ 文字目をそれぞれ $s_i$, $t_j$ と書くことにする。 削除した文字は一旦プールに入れておくということにする。

後ろから文字を比較していって

void solve() {
    int N;
    cin >> N;
    string S, T;
    cin >> S >> T;

    ll ans = 0;
    map<char, int> store;
    int tl = N - 1, sh = 0, sl = N - 1;
    while (tl >= 0 && sl >= 0 && sh <= sl) {
        if (S[sl] == T[tl]) {
            tl--, sl--;
        } else if (store[T[tl]]) {
            store[T[tl]]--;
            tl--;
        } else {
            while (sh <= sl) {
                ans++;
                if (S[sh] == T[tl]) {
                    sh++, tl--;
                    break;
                } else {
                    store[S[sh]]++;
                    sh++;
                }
            }
            if (sh > sl) {
                cout << -1 << endl;
                return;
            }
        }
    }

    cout << ans << endl;
}