<-- home

AtCoder ABC110 C

April 22, 2020

https://atcoder.jp/contests/abc110/tasks/abc110_c

ABC110 C - String transformationを解説と異なる方針で解いたのでメモ。

文字列Sを、文字列S内に含まれる’a’のインデックスの集合, ‘b’のインデックスの集合,…と表して、それぞれの集合を順にS(a), S(b),…とする。文字列Tについても同様にT(a), T(b),…を定義する。こうして文字列Sを表すと、2つの異なる英小文字c1とc2を選んでおこなう「操作」は、S(c1)とS(c2)をスワップすることと同じになる。したがって、文字列Sに「操作」を繰り返して、文字列Tを得られるかどうかは、

が成り立つかどうかと同値になる。

実装

// テンプレ省略
#define N_ALPHABET 26

using P = pair<i64, vector<i64>>;  // <インデックスの最小値, インデックス>
P S1[N_ALPHABET];
P S2[N_ALPHABET];

int main() {
    string s, t; cin >> s >> t;
    i64 L = s.length();

    vector<bool> seen(N_ALPHABET, false);
    REP(i, L) {
        i64 idx = s[i] - 'a';
        if (!seen[idx]) S1[idx].first = i;
        S1[idx].second.pb(i);
    }
    fill(seen.begin(), seen.end(), false);
    REP(i, L) {
        i64 idx = t[i] - 'a';
        if (!seen[idx]) S2[idx].first = i;
        S2[idx].second.pb(i);
    }

    sort(S1, S1 + N_ALPHABET);
    sort(S2, S2 + N_ALPHABET);

    bool ok = true;
    REP(i, N_ALPHABET) {
        if (S1[i].second != S2[i].second) {
            ok = false;
            break;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;

    return 0;
}