11.03.2024
791. Custom Sort String medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/535
Problem TLDR
Construct string from s
using order
#medium
Intuition
Two ways to solve: use sort (we need a stable sort algorithm), or use frequency.
Approach
When using sort, take care of -1
case.
When using frequency, we can use it as a counter too (-= 1
).
Complexity
Time complexity:
O(n), or nlog(n) for sortingSpace complexity:
O(n)
Code
fun customSortString(order: String, s: String) = s
.toMutableList()
.sortedBy { order.indexOf(it).takeIf { it >= 0 } ?: 200 }
.joinToString("")
pub fn custom_sort_string(order: String, s: String) -> String {
let (mut freq, mut res) = (vec![0; 26], String::new());
for b in s.bytes() { freq[(b - b'a') as usize] += 1 }
for b in order.bytes() {
let i = (b - b'a') as usize;
while freq[i] > 0 { freq[i] -= 1; res.push(b as char) }
}
for b in s.bytes() {
if freq[(b - b'a') as usize] > 0 { res.push(b as char) }
}; res
}