Chuỗi nhị phân đặc biệt trong C ++

Giả sử chúng ta có một chuỗi nhị phân không gian. Chuỗi này có một số thuộc tính sau -

• Có cùng số 0 và 1

• Mọi Tiền tố trong chuỗi nhị phân có ít nhất nhiều nhất là 1s 0

Bây giờ, giả sử chúng ta có chuỗi đặc biệt S, một động thái thực sự là chọn hai chuỗi con đặc biệt, không rỗng, liên tiếp của S và hoán đổi chúng.

Chúng ta phải tìm ra chuỗi kết quả lớn nhất về mặt từ vựng có thể, ở cuối bất kỳ số lần di chuyển nào.

Vì vậy, nếu đầu vào là 11011000, thì đầu ra sẽ là 11100100, điều này là do:Các chuỗi con "10" và "1100" được hoán đổi vị trí. Đây là chuỗi từ điển lớn nhất có thể sau vài lần di chuyển.

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

• Xác định một hàm makeLargestSpecial (), điều này sẽ mất s,

• ret:=chuỗi trống

• Xác định một mảng v chuỗi

• i:=0

• để khởi tạo j:=0, cnt:=0, khi j

  • nếu s [j] giống với '1' thì -

    • (tăng cnt lên 1)

  • Nếu không

    • (giảm cnt đi 1)

  • nếu cnt giống 0, thì -

    • chèn "1" + makeLargestSpecial (chuỗi con của s từ chỉ mục i + 1 đến j - i - 1) vào cuối v

    • i:=j + 1

• sắp xếp mảng v.r

• để khởi tạo i:=0, khi i

  • ret:=ret + v [i]

• trả lại ret

• Từ phương thức chính, hãy gọi makeLargestSpecial () với chuỗi.

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string makeLargestSpecial(string s) {
      string ret = "";
      vector<string> v;
      int i = 0;
      for (int j = 0, cnt = 0; j < s.size(); j++) {
         if (s[j] == '1') {
            cnt++;
         }
         else
         cnt--;
         if (cnt == 0) {
            v.push_back("1" + makeLargestSpecial(s.substr(i + 1,
            j - i - 1)) + "0");
            i = j + 1;
         }
      }
      sort(v.rbegin(), v.rend());
      for (int i = 0; i < v.size(); i++)
      ret += v[i];
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.makeLargestSpecial("11011000"));
}

Đầu vào

11011000

Đầu ra

11100100