Problem Statement
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return “” if not possible.
Example:
Input 1: s = "aaaaaabbbc" Output 1: "" Input 2: s = "aaaaabbbc" Output 2: "abababaca"
Code
Java
C++
Python
import java.util.*;
class Innoskrit {
public static String rearrangeString(String str) {
Map<Character, Integer> freqMap = new HashMap<>();
for (char chr : str.toCharArray())
freqMap.put(chr, freqMap.getOrDefault(chr, 0) + 1);
PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<Map.Entry<Character, Integer>>(
(e1, e2) -> e2.getValue() - e1.getValue());
maxHeap.addAll(freqMap.entrySet());
StringBuilder result = new StringBuilder(str.length());
while (maxHeap.size() >= 2) {
Map.Entry<Character, Integer> entry1 = maxHeap.poll();
Map.Entry<Character, Integer> entry2 = maxHeap.poll();
result.append(entry1.getKey());
result.append(entry2.getKey());
entry1.setValue(entry1.getValue() - 1);
entry2.setValue(entry2.getValue() - 1);
if(entry1.getValue() > 0) {
maxHeap.offer(entry1);
}
if(entry2.getValue() > 0) {
maxHeap.offer(entry2);
}
}
if(maxHeap.size() == 0) {
return result.toString();
} else {
Map.Entry<Character, Integer> entry = maxHeap.poll();
if(entry.getValue() == 1) {
result.append(entry.getKey());
return result.toString();
} else {
return "";
}
}
}
public static void main(String[] args) {
System.out.println(Innoskrit.rearrangeString("aaaaaabbbc"));
System.out.println(Innoskrit.rearrangeString("aaaaabbbc"));
}
}
#include <bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
struct comparator {
bool operator()(const pair<char, int> &x, const pair<char, int> &y) {
return x.second < y.second;
}
};
static string rearrangeString(string s) {
unordered_map<char, int> freqMap;
for(char ch : s) {
freqMap[ch]++;
}
priority_queue<pair<char, int>, vector<pair<char, int>>, comparator> maxHeap;
for(auto entry : freqMap) {
maxHeap.push(entry);
}
string result = "";
while(maxHeap.size() >= 2) {
pair<char, int> entry1 = maxHeap.top();
maxHeap.pop();
pair<char, int> entry2 = maxHeap.top();
maxHeap.pop();
result += entry1.first;
result += entry2.first;
entry1.second--;
entry2.second--;
if(entry1.second > 0) {
maxHeap.push(entry1);
}
if(entry2.second > 0) {
maxHeap.push(entry2);
}
}
if(maxHeap.size() == 0) {
return result;
} else {
pair<char, int> entry = maxHeap.top();
maxHeap.pop();
if(entry.second == 1) {
result += entry.first;
return result;
} else {
return "";
}
}
}
};
int main() {
cout << Innoskrit::rearrangeString("aaaaaabbbc") << endl;
cout << Innoskrit::rearrangeString("aaaaabbbc") << endl;
return 0;
}
from heapq import *
class Pair:
def __init__(self, char, freq):
self.char = char
self.freq = freq
def __lt__(self, other):
return self.freq > other.freq
class Innoskrit:
@staticmethod
def rearrange_string(string):
freq_map = dict()
for char in string:
freq_map[char] = freq_map.get(char, 0) + 1
max_heap = []
for char, freq in freq_map.items():
heappush(max_heap, Pair(char, freq))
result = []
while len(max_heap) >= 2:
entry1 = heappop(max_heap)
entry2 = heappop(max_heap)
result.append(entry1.char)
result.append(entry2.char)
entry1.freq -= 1
entry2.freq -= 1
if entry1.freq > 0:
heappush(max_heap, entry1)
if entry2.freq > 0:
heappush(max_heap, entry2)
if len(max_heap) == 0:
return "".join(result)
else:
entry = heappop(max_heap)
if entry.freq == 1:
result += entry.char
return "".join(result)
else:
return ""
if __name__ == '__main__':
print(Innoskrit.rearrange_string("aaaaaabbbc"))
print(Innoskrit.rearrange_string("aaaaabbbc"))
Output:
"" abababaca
Time and Space Complexity
Time Complexity: The time complexity of the above algorithm is O(N∗logN) where ‘N’ is the number of characters in the input string.
Space Complexity: The space complexity will be O(N), as in the worst case, we need to store all the ‘N’ characters in the HashMap.