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: ""
use the frequency map
create a heap a sorted order based on the frequency, so we exhaust the char with highest frequency with 2nd highest
iterate over the frequency map until all the elements are exhausted
At any point the frequency of last character is same as current character and we dont have any other character to work with
return ""
let n = s.length
let map = new Map()
for (let i = 0; i < n; i++) {
map.set(s[i], (map.get(s[i]) || 0) + 1)
}
let maxHeap = []
for (let [char, count] of map) {
maxHeap.push({ char, count })
}
maxHeap.sort((a, b) => b.count - a.count)
let result = []
while (0 < maxHeap.length) {
const first = maxHeap.shift()
if (result.length === 0
|| result[result.length - 1] !== first.char) {
result.push(first.char)
first.count--
if (0 < first.count) {
maxHeap.push(first)
}
} else {
if (maxHeap.length === 0) {
return ""
}
let second = maxHeap.shift()
result.push(second.char)
second.count--
if (0 < second.count) {
maxHeap.push(second)
}
maxHeap.unshift(first)
}
maxHeap.sort((a, b) => b.count - a.count)
}
return result.join('')
This can be optimised further:
Time Complexity:
O(N) + O(N) + O(NlogN)
For the while ( 0 < maxHeap)
O(N) iterations × O(K log K) per sort = O(N × K log K)
Total : N * K Log K
now instead of shift and unshift , can we use push and pop??
maxHeap.sort((a, b) => a.count - b.count)
let result = []
while (0 < maxHeap.length) {
const first = maxHeap.pop()
if (result.length === 0
|| result[result.length - 1] !== first.char) {
result.push(first.char)
first.count--
if (0 < first.count) {
maxHeap.push(first)
}
} else {
if (maxHeap.length === 0) {
return ""
}
let second = maxHeap.pop()
result.push(second.char)
second.count--
if (0 < second.count) {
maxHeap.push(second)
}
maxHeap.push(first)
}
maxHeap.sort((a, b) => a.count - b.count)
}
return result.join('')
if we build and use a real heap instead of using fake heap as an array and sorting every time. We can futher reduce the complexity as heap maitains the order while inserting and avoids resorting the element like we are manually doing it at the end of the iteration.
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:
Example 2:
let n = s.length let map = new Map() for (let i = 0; i < n; i++) { map.set(s[i], (map.get(s[i]) || 0) + 1) }let maxHeap = [] for (let [char, count] of map) { maxHeap.push({ char, count }) } maxHeap.sort((a, b) => b.count - a.count)let result = [] while (0 < maxHeap.length) { const first = maxHeap.shift() if (result.length === 0 || result[result.length - 1] !== first.char) { result.push(first.char) first.count-- if (0 < first.count) { maxHeap.push(first) } } else { if (maxHeap.length === 0) { return "" } let second = maxHeap.shift() result.push(second.char) second.count-- if (0 < second.count) { maxHeap.push(second) } maxHeap.unshift(first) } maxHeap.sort((a, b) => b.count - a.count) }return result.join('')This can be optimised further:
Time Complexity:
now instead of shift and unshift , can we use push and pop??
let result = [] while (0 < maxHeap.length) { const first = maxHeap.pop() if (result.length === 0 || result[result.length - 1] !== first.char) { result.push(first.char) first.count-- if (0 < first.count) { maxHeap.push(first) } } else { if (maxHeap.length === 0) { return "" } let second = maxHeap.pop() result.push(second.char) second.count-- if (0 < second.count) { maxHeap.push(second) } maxHeap.push(first) } maxHeap.sort((a, b) => a.count - b.count) } return result.join('')if we build and use a real heap instead of using fake heap as an array and sorting every time. We can futher reduce the complexity as heap maitains the order while inserting and avoids resorting the element like we are manually doing it at the end of the iteration.