Hoán đổi tối thiểu để tạo chuỗi bằng nhau trong C ++

Giả sử chúng ta có hai chuỗi s1 và s2 có độ dài bằng nhau chỉ gồm các chữ cái "x" và "y". Nhiệm vụ của chúng ta là làm sao cho hai chuỗi này bằng nhau. Chúng ta có thể hoán đổi hai ký tự bất kỳ thuộc các chuỗi khác nhau, có nghĩa là - hoán đổi s1 [i] và s2 [j]. Chúng ta phải tìm số lượng hoán đổi tối thiểu cần thiết để làm cho s1 và s2 bằng nhau, hoặc trả về -1 nếu không thể làm như vậy. Vì vậy, nếu các chuỗi là s1 =“xy” và s2 =“yx”, thì đầu ra sẽ là 2. Nếu chúng ta hoán đổi s1 [0] và s2 [0], s1 ="yy", s2 ="xx". Sau đó hoán đổi s1 [0] và s2 [1], s1 ="xy", s2 ="xy".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Đặt x1, x2, y1 và y2 là 0
• cho tôi trong phạm vi từ 0 đến kích thước của s1
  • a:=s1 [i] và b:=s2 [i]
  • nếu a không giống b, thì
    • nếu a =‘x’ thì tăng x1, ngược lại thì tăng y1 thêm 1
    • nếu b =‘x’ thì tăng x2, ngược lại thì tăng y2 thêm 1
• nếu (x1 + x2) là số lẻ hoặc (y1 + y2) là số lẻ, thì trả về -1
• trả về x1 / 2 + y1 / 2 + (x1 mod 2) * 2

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
   }
};
main(){
   Solution ob;
   cout <<ob.minimumSwap("xy", "yx");
}

Đầu vào

"xy"
"yx"

Đầu ra

2