Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k apart. If no such arrangement is possible, return an empty string.
Table of Contents
Sample Input/Output:
Let’s consider a sample input:
s = "aabbcc"
k = 3
Expected Output:
"abcabc"
Explanation:
For the given input s = “aabbcc” and k = 3, one possible rearrangement is “abcabc”, where the same characters are at least 3 distance apart.
Time and Space Complexity:
The time complexity of the solution will be O(N log A), where N is the length of the string s, and A is the size of the alphabet (number of unique characters in the string).
The space complexity will be O(A) to store the frequency of each character in the frequency array.
C++ Solution:
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
string rearrangeString(string s, int k) {
if (k <= 1) {
return s; // No need to rearrange if k <= 1
}
vector<int> freq(26, 0);
for (char ch : s) {
freq[ch - 'a']++;
}
priority_queue<pair<int, char>> maxHeap;
for (int i = 0; i < 26; ++i) {
if (freq[i] > 0) {
maxHeap.push({freq[i], 'a' + i});
}
}
string result = "";
while (!maxHeap.empty()) {
vector<pair<int, char>> temp; // Temporary storage for characters to be re-added after k distance
int count = min(k, static_cast<int>(s.size() - result.size()));
for (int i = 0; i < count; ++i) {
if (maxHeap.empty()) {
return ""; // No valid rearrangement possible
}
auto curr = maxHeap.top();
maxHeap.pop();
result += curr.second;
if (--curr.first > 0) {
temp.push_back(curr);
}
}
for (auto& t : temp) {
maxHeap.push(t);
}
}
return result;
}
int main() {
string s = "aabbcc";
int k = 3;
string result = rearrangeString(s, k);
cout << "Rearranged String: " << result << endl;
return 0;
}
In this implementation, we first create a frequency array to count the occurrences of each character in the string. Then, we use a max-heap to store characters based on their frequencies in descending order. In each iteration, we pop the most frequent character from the heap and add it to the result string. We also keep a temporary storage temp for characters that will be re-added after k distance.
The main function demonstrates the usage of rearrangeString by rearranging the string according to the given input s and k.
The output for the provided test case will be:
Rearranged String: abcabc