# 03.11.2023 [767. Reorganize String]
Non repeating consequent chars string from another string
03.11.2023
767. Reorganize String medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/391
Problem TLDR
Non-repeating consequent chars string from another string
Intuition
The naive brute force solution is to do Depth-First Search and memoization by given current char, previous one and used chars set. It gives TLE, as it takes O(n^3).
Next, use hint
.
To take chars one by one from the two most frequent, we will use a Priority Queue
Approach
if previous is equal to the current and there is no other chars - we can’t make a result
consider appending in a single point of code to simplify the solution
use Kotlin’s API:
buildString
,compareByDescending
,onEach
Complexity
Time complexity:
O(n), assume constant128log(128)
for a Heap sortingSpace complexity:
O(n)
Code
fun reorganizeString(s: String): String = buildString {
val freq = IntArray(128)
s.onEach { freq[it.toInt()]++ }
val pq = PriorityQueue<Char>(compareByDescending { freq[it.toInt()] })
for (c in 'a'..'z') if (freq[c.toInt()] > 0) pq.add(c)
while (pq.isNotEmpty()) {
var c = pq.poll()
if (isNotEmpty() && last() == c) {
if (pq.isEmpty()) return ""
c = pq.poll()
pq.add(last())
}
append(c)
if (--freq[c.toInt()] > 0) pq.add(c)
}
}