Sort clothing sizes S, M and L in one pass

You get a string of clothing sizes, one character per item, using only S, M and L. Return the same items sorted from smallest to largest. The expected answer runs in linear time; a comparison sort is the starting point, not the finish.

Interface

Unless you agree on a different interface with the interviewer, assume:

• sort_sizes(sizes: str) -> str — returns the characters of sizes ordered S, then M, then L.

Example

sort_sizes("LSMSLM")  ->  "SSMMLL"
sort_sizes("MMM")     ->  "MMM"
sort_sizes("")        ->  ""

Constraints

• 0 <= len(sizes) <= 10^6.
• In the base problem only S, M and L appear.

Clarifying questions

• Can the input contain any other character, and what should happen to it: error, drop, or put at the end?
• Is the input a string of single characters or a list of tokens such as XS and XXL?
• Should the function return a new string or sort a mutable array in place?
• Is the order of sizes fixed, or passed in?

What a strong answer covers

• Counting: one pass to count each size, one pass to write the result. O(n) time, O(1) extra space beyond the output.
• Or the three-way partition (Dutch national flag) when sorting an array in place.
• Why a comparison sort with a custom key is O(n log n) and what it is still good for.
• Building the output without repeated string concatenation.
• Tests: empty input, one size only, already sorted, reverse sorted, one million characters.

Follow-ups

• Take the size order as a parameter, for example ["XS", "S", "M", "L", "XL", "XXL"], with tokens of different lengths.
• Sizes such as XXXS or 4XL with any number of Xs. Define a sort key without listing every size.
• An unknown size appears. Decide and implement the behavior.