160. House Alphabet
A club has its own alphabet. The string order lists lower case letters in the club's order of importance; if a letter is listed more than once, only its first position counts. Given the string s, rearrange its characters so that they follow the club's order: all copies of the first listed letter, then all copies of the second listed letter, and so on.
Letters of s that do not appear in order are placed after all the listed ones, in the normal alphabetical order. Return the rearranged string, which has exactly the same characters as s. Counting the letters is faster than comparing characters one by one.
Example 1
- Input:
- order = "hxz", s = "zhxhzbxa"
- Output:
- "hhxxzzab"
- Explanation:
The listed letters come as hh, xx, zz; the unlisted letters a and b follow alphabetically, giving hhxxzzab.
Example 2
- Input:
- order = "qwerty", s = "typewriter"
- Output:
- "weerrttyip"
- Explanation:
The listed letters give w, ee, rr, tt, y; the unlisted i and p follow, giving weerrttyip.
Constraints
1 ≤ order.length, s.length ≤ 105
order and s contain only lower case letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(1)