#791
Custom Sort String
Medium Counting by custom order
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
order lists some unique letters in a custom order. Rearrange s so that letters in order appear in that order; other letters can go anywhere.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: reorder s to follow the letter order in order.
Why this works: count letters of s, write them in order's sequence, then the rest.
Example: order "cba", s = "abcd"
c, b, a, then d → "cbad"✦Hints open one at a time
Count the letters in s.
Output letters in order's sequence, then everything else.
↗Approach
A counting sort keyed by the custom order: write each letter of order count times, then the remaining letters.
</>Solution (Java)
class Solution {
public String customSortString(String order, String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
StringBuilder sb = new StringBuilder();
for (char c : order.toCharArray()) {
while (count[c - 'a']-- > 0) sb.append(c);
}
for (char c = 'a'; c <= 'z'; c++) {
while (count[c - 'a']-- > 0) sb.append(c);
}
return sb.toString();
}
}!Common mistake
Using a comparator on Character objects with indexOf — slower and more code.
Complexity
- Time: O(|s| + |order|).
- Space: O(26).
Topic: Sorting
🎬 Episodes 24–28: video coming soon