Tổ chức lại chuỗi trong C ++

Giả sử chúng ta có một chuỗi S, hãy kiểm tra xem các chữ cái có thể được sắp xếp lại sao cho hai ký tự nằm liền kề nhau không giống nhau hay không. Nếu điều đó là có thể, hãy xuất ra bất kỳ kết quả nào có thể. Nếu không được, hãy trả về chuỗi trống. Vì vậy, nếu đầu vào giống như "AAB", thì đầu ra sẽ là "ABA".

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

• Tạo một hàng đợi ưu tiên gồm các cặp ký tự số nguyên được gọi là pq, xác định một bản đồ m
• n:=kích thước của chuỗi
• lưu trữ tần số ký tự trong bản đồ m
• cho mỗi cặp khóa-giá trị p trong m
  • insert (phần nguyên của p, phần ký tự của p)
• ans:=chuỗi trống
• trong khi pq không trống
  • đặt một:=cặp trên cùng khỏi pq và xóa cặp trên cùng khỏi pq
  • nếu pq trống, thì
    • nếu phần nguyên của một> 1, thì trả về chuỗi trống
    • ans:=ans + phần ký tự của một phần
    • trả lại ans
  • hai:=cặp hàng đầu khỏi pq và xóa cặp hàng đầu khỏi pq
  • ans:=ans + phần ký tự của một phần
  • ans:=ans + một phần ký tự của hai phần
  • tăng phần nguyên của một và hai lên 1
  • nếu phần nguyên của một phần không phải là 0, thì hãy chèn một phần vào pq
  • nếu phần nguyên của hai không phải là 0, thì hãy chèn một phần vào pq
• trả lại ans

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 reorganizeString(string S) {
      priority_queue <pair <int, char>> pq;
      map <char, int> m;
      int n = S.size();
      for(int i = 0; i < n; i++){
         m[S[i]]++;
      }
      map <char, int> :: iterator i = m.begin();
      while(i != m.end()){
         pq.push({i->second, i->first});
         i++;
      }
      string ans = "";
      while(!pq.empty()){
         pair <int, char> one = pq.top();
         pq.pop();
         if(pq.empty()){
            if(one.first > 1)
            return "";
            ans += one.second;
            return ans;
         }
         pair <int, char> two = pq.top();
         pq.pop();
         ans += one.second;
         ans += two.second;
         //cout << ans << endl;
         one.first--;
         two.first--;
         if(one.first)pq.push(one);
         if(two.first)pq.push(two);
      }
      return ans;
   }
};
int main() {
   Solution ob1;
   cout << ob1.reorganizeString("AAB") << endl;
   return 0;
}

Đầu vào

S = "AAB"
ob1.reorganizeString("AAB")

Đầu ra

ABA