Given two input strings: order and target.
Given two input strings: order and target. The order string defines a custom character ordering (similar to the alien dictionary problem). Sort the characters in target according to the precedence defined by order. The solution is expected to run in linear time O(n) with respect to the length of target.
Can you achieve linear time complexity O(n)?
What if there are characters in target that don't appear in order? How do you handle them?
| Approach | Notes |
|---|---|
| Comparison-based sort with custom comparator | Simple to implement — build a rank map then sort target using that map as the comparator key. Time complexity is O(n log n), which does not meet the linear time requirement. |
Common mistakes: Failing to achieve linear time complexity for the sort — at least one candidate did not reach a linear solution and was noted as failing specifically on that requirement.
Interviewer hints: The interviewer explicitly required linear sorting time O(n) with respect to the length of target, and this was a hard requirement that determined pass/fail.