Sắp xếp lại chuỗi k Khoảng cách ngoài trong C ++

Giả sử chúng ta có một chuỗi không rỗng s và một số nguyên k; chúng ta phải sắp xếp lại chuỗi sao cho các ký tự giống nhau cách nhau ít nhất k. Các chuỗi đã cho có dạng chữ thường. Nếu không có cách nào để sắp xếp lại các chuỗi, thì chúng ta sẽ là một chuỗi trống.

Vì vậy, nếu đầu vào là s =​​"aabbcc", k =3, thì đầu ra sẽ là "abcabc", điều này là do các chữ cái giống nhau cách nhau ít nhất 3 khoảng cách.

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

• ret:=một chuỗi trống

• Xác định một bản đồ m

• n:=kích thước của s

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

  • (tăng m [s [i]] lên 1)

• Xác định một hàng đợi ưu tiên pq

• đối với mỗi cặp khóa-giá trị, nó bằng m, do -

  • temp:=một cặp với khóa và giá trị của nó

  • chèn tạm thời vào pq

  • (tăng nó lên 1)

• Xác định một dq deque

• while (không phải pq trống), do -

  • curr:=top of pq

  • xóa phần tử khỏi pq

  • ret:=ret + curr.first

  • (giảm giới hạn giây xuống 1)

  • chèn curr vào cuối dq

  • nếu kích thước của dq> =k, thì -

    • curr:=phần tử đầu tiên của dq

    • xóa phần tử phía trước khỏi dq

    • nếu curr.second> 0, thì -

      • chèn curr vào pq

• while (không phải dq trống và phần tử đầu tiên của dq giống 0), do -

  • xóa phần tử phía trước khỏi dq

• return (nếu dq trống thì hãy ret, nếu không thì chuỗi trống)

Ví dụ

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;
struct Comparator {
   bool operator()(pair<char, int> a, pair<char, int> b) {
      return !(a.second > b.second);
   }
};
class Solution {
public:
   string rearrangeString(string s, int k) {
      string ret = "";
      unordered_map<char, int> m;
      int n = s.size();
      for (int i = 0; i < n; i++) {
         m[s[i]]++;
      }
      unordered_map<char, int>::iterator it = m.begin();
      priority_queue<pair<char, int<, vector<pair<char, int>>,
      Comparator> pq;
      while (it != m.end()) {
         pair<char, int> temp = {it->first, it->second};
         pq.push(temp);
         it++;
      }
      deque<pair<char, int>> dq;
      while (!pq.empty()) {
         pair<char, int> curr = pq.top();
         pq.pop();
         ret += curr.first;
         curr.second--;
         dq.push_back(curr);
         // cout << ret << " " << dq.size() << endl;
         if (dq.size() >= k) {
            curr = dq.front();
            dq.pop_front();
            if (curr.second > 0)
            pq.push(curr);
         }
      }
      while (!dq.empty() && dq.front().second == 0)
         dq.pop_front();
      return dq.empty() ? ret : "";
   }
};
main() {
   Solution ob;
   cout << (ob.rearrangeString("aabbcc", 3));
}

Đầu vào

"aabbcc", 3

Đầu ra

bacbac