Submission

Score: 0

User: pxsit

Problemset: 04.Corretc the wodr

Language: cpp

Time: 0.002 second

Submitted On: 2025-06-01 11:05:15

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    while (n--) {
        string s1, s2;
        cin >> s1 >> s2;
        if (s1.size() != s2.size()) {
            cout << "Cannot transform to " << s1 << '\n';
            continue;
        }
        vector<int> freq(256, 0);
        for (int i = 0; i < s1.size(); i++) {
            freq[(unsigned char)s1[i]]++;
            freq[(unsigned char)s2[i]]--;
        }
        bool ok = true;
        for (int c = 0; c < 256; c++) {
            if (freq[c] != 0) { ok = false; break; }
        }
        if (!ok) {
            cout << "Cannot transform to " << s1 << '\n';
            continue;
        }

        // --- NEW: build a permutation on mismatched indices and count cycles ---
        int L = s1.size();
        vector<vector<int>> want(256);
        vector<int> mismatch;
        for (int i = 0; i < L; i++) {
            if (s1[i] != s2[i]) {
                want[(unsigned char)s1[i]].push_back(i);
                mismatch.push_back(i);
            }
        }
        int M = mismatch.size();
        vector<int> to(L, -1);
        // assign each mismatch in s2 to a target in s1
        for (int i : mismatch) {
            int c = (unsigned char)s2[i];
            int j = want[c].back(); 
            want[c].pop_back();
            to[i] = j;
        }
        vector<bool> seen(L,false);
        int cycles = 0;
        for (int i : mismatch) {
            if (!seen[i]) {
                // walk this cycle
                int cur = i;
                do {
                    seen[cur] = true;
                    cur = to[cur];
                } while (!seen[cur]);
                cycles++;
            }
        }
        // each cycle of length ℓ uses ℓ–1 swaps
        cout << (M - cycles) << '\n';
    }
}