Sort a String of Clothing Sizes
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
# Sort a String of Clothing Sizes
## Problem
You are given a string `sizes` in which every character is one clothing size: `S`, `M`, or `L`. Return a new string containing the same characters sorted in the order `S`, then `M`, then `L`.
Implement:
```python
def sort_sizes(sizes: str) -> str:
...
```
## Constraints
- `0 <= len(sizes) <= 1_000_000`
- Every character in `sizes` is one of `S`, `M`, and `L`.
- The input string may be empty.
- Aim for `O(n)` time.
## Examples
```text
sort_sizes("LMSMSL") -> "SSMMLL"
sort_sizes("MMM") -> "MMM"
sort_sizes("") -> ""
```
## Extension
After solving the fixed three-size version, explain how you would support a caller-provided ordering such as `['XS', 'S', 'M', 'L', 'XL']` when the input is a list of size tokens. Define whether unknown tokens should be rejected or ignored, and justify that choice.
Quick Answer: Sort a string containing only S, M, and L into size order in linear time. Extend the discussion to custom token orderings, unknown-size behavior, empty inputs, and a million-character performance bound.
Given a string containing only S, M, and L size characters, return a new string with the same characters ordered as all S values, then M values, then L values.
Constraints
- The input contains only S, M, and L.
- The input may be empty.
- Preserve the multiplicity of every size.
- Aim for O(n) time.
- Return a new string.
Examples
Input: ("",)
Expected Output: ''
Explanation: The empty string remains empty.
Input: ("LMSMSL",)
Expected Output: 'SSMMLL'
Explanation: Mixed sizes are grouped in the required order.
Hints
- Only three distinct values need to be ordered.
- Count each size during one scan.
- Build the result from repeated blocks in the required order.