Solution For Reorganize String
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 1:
Input: s = “aab”
Output: “aba”
Example 2:
Input: s = “aaab”
Output: “”
Approach:
The problem requires us to rearrange the input string such that no two adjacent characters are the same. We can approach the problem in the following way:
First, we need to count the frequency of each character in the input string s. We can do this by creating a hash table that will store the count of each character.
Next, we need to sort the characters in decreasing order of frequency. We can do this by creating a priority queue that will sort the characters based on their count.
We can now start constructing the result string by appending the most frequent character to the result string first. Then we can append the next most frequent character to the result string, but only if it is not the same as the last character in the result string. We repeat this process until the result string is fully constructed.
If at any point we encounter a character that cannot be added to the result string without violating the condition of not having two adjacent characters that are the same, we return “”.
Solution:
class Solution {
public:
string reorganizeString(string s) {
// Count the frequency of each character in the string
unordered_map<char, int> countMap;
for (char c : s) {
countMap[c]++;
}
// Create a priority queue to sort the characters in decreasing order of frequency
priority_queue<pair<int, char>> pq;
for (auto it : countMap) {
pq.push({it.second, it.first});
}
// Construct the result string
string result = "";
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
if (result.empty() || curr.second != result.back()) {
result += curr.second;
if (--curr.first > 0) {
pq.push(curr);
}
} else {
return "";
}
}
return result;
}
};
Complexity Analysis:
Time Complexity: O(nlogn), where n is the length of the input string s. We need to count the frequency of each character in the input string s which takes O(n) time. Sorting the characters in decreasing order of frequency using a priority queue takes O(nlogn) time in the worst case. Constructing the final string also takes O(n) time.
Space Complexity: O(n), where n is the length of the input string s. We need to store the count of each character in the input string s in a hash table which takes O(n) space. We also need to use a priority queue to sort the characters, which can take up to O(n) space in the worst case.
Step by Step Implementation For Reorganize String
class Solution {
public String reorganizeString(String S) {
// TODO: Implement solution
}
}class Solution:
def reorganizeString(self, S: str) -> str:
# create a list of tuples (letter, count)
counts = collections.Counter(S).most_common()
# if the most common letter occurs more than half the time, it can't be rearranged
if counts[0][1] > (len(S) + 1) / 2:
return ""
# create a list of alternating letters starting with the most common one
ans = [c for c, _ in counts]
# fill in the remaining letters
i = 0
for c, _ in counts[1:]:
ans[i] += c
i += 2
if i >= len(ans):
i = 1
return "".join(ans)var reorganizeString = function(S) {
// create a map to store the frequencies of each character
let map = {};
for (let char of S) {
if (char in map) {
map[char]++;
} else {
map[char] = 1;
}
}
// create a min heap to store the characters in order of frequency
let heap = new MinHeap();
for (let char in map) {
heap.insert(char, map[char]);
}
// build up the new string, alternate between the most and second most frequent characters
let result = "";
let mostFreq = heap.extractMin();
let secondFreq = heap.extractMin();
while (mostFreq && secondFreq) {
for (let i = 0; i < Math.min(mostFreq[1], secondFreq[1]); i++) {
result += mostFreq[0];
result += secondFreq[0];
}
if (mostFreq[1] > secondFreq[1]) {
result += mostFreq[0];
}
mostFreq = heap.extractMin();
secondFreq = heap.extractMin();
}
// if there is only one character left in the heap, append it to the end of the string
if (mostFreq) {
result += mostFreq[0];
}
return result.length === S.length ? result : "";
};
class MinHeap {
constructor() {
this.heap = [];
}
insert(char, freq) {
this.heap.push([char, freq]);
this.heapifyUp(this.heap.length - 1);
}
heapifyUp(i) {
let parentIdx = this.getParentIdx(i);
if (parentIdx === -1) return;
if (this.heap[parentIdx][1] > this.heap[i][1]) {
this.swap(parentIdx, i);
this.heapifyUp(parentIdx);
}
}
extractMin() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
this.swap(0, this.heap.length - 1);
let min = this.heap.pop();
this.heapifyDown(0);
return min;
}
heapifyDown(i) {
let leftIdx = this.getLeftChildIdx(i);
let rightIdx = this.getRightChildIdx(i);
let smallestIdx = i;
if (leftIdx !== -1 && this.heap[leftIdx][1] < this.heap[smallestIdx][1]) {
smallestIdx = leftIdx;
}
if (rightIdx !== -1 && this.heap[rightIdx][1] < this.heap[smallestIdx][1]) {
smallestIdx = rightIdx;
}
if (smallestIdx !== i) {
this.swap(i, smallestIdx);
this.heapifyDown(smallestIdx);
}
}
getParentIdx(i) {
return i === 0 ? -1 : Math.floor((i - 1) / 2);
}
getLeftChildIdx(i) {
let leftIdx = 2 * i + 1;
return leftIdx >= this.heap.length ? -1 : leftIdx;
}
getRightChildIdx(i) {
let rightIdx = 2 * i + 2;
return rightIdx >= this.heap.length ? -1 : rightIdx;
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
}class Solution {
public:
string reorganizeString(string S) {
// create a map of character to count
unordered_map counts;
for (char c : S) {
counts[c]++;
}
// create a max heap of characters by count
priority_queue> pq;
for (auto& p : counts) {
pq.push({p.second, p.first});
}
// build the answer string
string ans;
while (!pq.empty()) {
// get the most frequent character
auto [count, c] = pq.top();
pq.pop();
// if this is the first character, append it
if (ans.empty()) {
ans += c;
count--;
}
// otherwise, check if the current character can be
// appended to the end of the answer string
else if (ans.back() != c) {
ans += c;
count--;
}
// if not, check if there is another character that can
// be appended to the end of the answer string
else if (!pq.empty()) {
auto [nextCount, nextC] = pq.top();
pq.pop();
// if so, append it and push the current character
// back into the heap
if (nextCount > 0) {
ans += nextC;
pq.push({count, c});
}
// otherwise, return an empty string since there is
// no way to rearrange the string
else {
return "";
}
}
// if not, return an empty string since there is
// no way to rearrange the string
else {
return "";
}
// if there are any remaining characters for this
// character, push it back into the heap
if (count > 0) {
pq.push({count, c});
}
}
return ans;
}
}; public class Solution {
public string ReorganizeString(string S) {
// Create a count array of the alphabet
int[] count = new int[26];
foreach (char c in S) {
count[c - 'a']++;
}
// Create a priority queue to store the characters by their count
PriorityQueue pq = new PriorityQueue();
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
pq.Add(new CharacterCount((char)(i + 'a'), count[i]));
}
}
// Build up the result string
StringBuilder sb = new StringBuilder();
while (pq.Count > 1) {
// Get the two most common characters
CharacterCount cc1 = pq.Remove();
CharacterCount cc2 = pq.Remove();
// Append them to the result string
sb.Append(cc1.c);
sb.Append(cc2.c);
// Decrement their counts and add them back to the queue
cc1.count--;
cc2.count--;
if (cc1.count > 0) pq.Add(cc1);
if (cc2.count > 0) pq.Add(cc2);
}
// If there is still one character left, append it to the end of the string
if (pq.Count == 1) {
CharacterCount cc = pq.Remove();
if (cc.count > 1) return "";
sb.Append(cc.c);
}
return sb.ToString();
}
}
class CharacterCount : IComparable {
public char c;
public int count;
public CharacterCount(char c, int count) {
this.c = c;
this.count = count;
}
public int CompareTo(CharacterCount other) {
return other.count - this.count;
}
}