LeetCode Entry
791. Custom Sort String
Construct string from s using order
791. Custom Sort String medium
blog post
substack
youtube
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 sorting
-
Space 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
}