การสลับน้อยที่สุดเพื่อทำให้สตริงเท่ากันใน C++

สมมติว่าเรามีสตริงสองตัว s1 และ s2 ความยาวเท่ากัน ประกอบด้วยตัวอักษร 'x' และ 'y' เท่านั้น เราต้องการทำให้สตริงทั้งสองเท่ากัน โดยสลับตัวอักษรระหว่างสตริงต่างกัน (swap s1[i] กับ s2[j]) หาจำนวนการสลับน้อยที่สุด หรือคืน -1 ถ้าไม่ทำได้

ตัวอย่าง: s1 = "xy", s2 = "yx" ผลลัพธ์: 2
สลับ s1[0] กับ s2[0] → s1="yy", s2="xx"
สลับ s1[0] กับ s2[1] → s1="xy", s2="xy"

ขั้นตอนการแก้ปัญหา

• นับ x1, x2, y1, y2 โดย:
  • x1 = จำนวนตำแหน่งที่ s1[i]='x' และ s2[i]!='x'
  • y1 = จำนวนตำแหน่งที่ s1[i]='y' และ s2[i]!='y'
  • x2 = จำนวนตำแหน่งที่ s2[i]='x' และ s1[i]!='x'
  • y2 = จำนวนตำแหน่งที่ s2[i]='y' และ s1[i]!='y'
• ถ้า (x1+x2) เป็นคี่ หรือ (y1+y2) เป็นคี่ คืน -1
• คืน x1/2 + y1/2 + (x1%2)*2

ตัวอย่างโค้ด (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];
            char 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");
}

อินพุต

"xy" "yx"

เอาต์พุต

2