Số lần hoán đổi tối thiểu để hai chuỗi bằng nhau trong C++

Cho hai chuỗi s1, s2 cùng độ dài, chỉ chứa 'x' và 'y'. Có thể hoán đổi s1[i] và s2[j]. Tìm số hoán đổi tối thiểu để s1 == s2, trả về -1 nếu không thể.

Ví dụ: s1="xy", s2="yx" → Kết quả: 2. Hoán đổi s1[0] với s2[0] → "yy"/"xx", rồi s1[0] với s2[1] → "xy"/"xy".

Giải thuật (Đếm cặp khác nhau)

1. Đếm: x1 (s1='x', s2='y'), y1 (s1='y', s2='x'), x2, y2.
2. Nếu (x1+x2) lẻ hoặc (y1+y2) lẻ → trả về -1.
3. Kết quả: x1/2 + y1/2 + (x1%2)*2.
4. Giải thích: cặp (x,y) và (y,x) giải quyết bằng 1 hoán đổi; cặp còn dư (x,y)+(x,y) cần 2 hoán đổi.

Ví dụ C++

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

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
        for(int i = 0; i < s1.size(); i++) {
            char a = s1[i], b = s2[i];
            if(a != b) {
                if(a == 'x') x1++; else y1++;
                if(b == 'x') x2++; else y2++;
            }
        }
        if ((x1 + x2) & 1 || (y1 + y2) & 1) return -1;
        return x1/2 + y1/2 + (x1 % 2) * 2;
    }
};

int main() {
    Solution ob;
    cout << ob.minimumSwap("xy", "yx");
    return 0;
}

Đầu vào

"xy" "yx"

Đầu ra

2