สมมติว่าเรามีสตริงไม่ว่าง s และจำนวนเต็ม k เราต้องจัดเรียงสตริงใหม่ให้ตัวอักษรเดียวกันห่างกันอย่างน้อย k ตัวอักษร สตริงที่ให้มาประกอบด้วยตัวอักษรพิมพ์เล็ก หากจัดเรียงไม่ได้ ให้คืนสตริงว่าง
เช่น ถ้าอินพุตคือ s = "aabbcc", k = 3 ผลลัพธ์จะเป็น "abcabc" เพราะตัวอักษรซ้ำห่างกันอย่างน้อย 3 ตัว
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
- ret := สตริงว่าง
- สร้าง map m นับความถี่ตัวอักษรใน s
- สร้าง priority queue pq เรียงตามความถี่มากไปน้อย (max-heap)
- สร้าง deque dq เก็บค่าที่ใช้ไปชั่วคราว
- while pq ไม่ว่าง: ดึง curr จาก pq เพิ่ม curr.first เข้า ret ลด curr.second ลง 1 ใส่ curr เข้า dq; ถ้า dq.size() >= k: ดึง front ของ dq ถ้า count > 0 ใส่กลับ pq
- หลังจบ while: ลบ front ของ dq ที่ count==0; ถ้า dq ว่าง คืนค่า ret มิฉะนั้นคืนค่าว่าง
ตัวอย่าง
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
#include <bits/stdc++.h>
using namespace std;
struct Comparator {
bool operator()(pair a, pair b) { return !(a.second > b.second); }
};
class Solution {
public:
string rearrangeString(string s, int k) {
string ret = "";
unordered_map m;
int n = s.size();
for (int i = 0; i < n; i++) m[s[i]]++;
priority_queue, vector>, Comparator> pq;
for (auto& it : m) pq.push({it.first, it.second});
deque> dq;
while (!pq.empty()) {
auto curr = pq.top(); pq.pop();
ret += curr.first; curr.second--;
dq.push_back(curr);
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));
}
อินพุต
"aabbcc", 3
เอาต์พุต
bacbac
