Reorganize String
Real-world version: Paint Line ShuffleThe statement here is our own: the same inputs, outputs and technique.
A paint line feeds car bodies through one spray booth. Every body queued for today carries a one-letter colour code, and the whole queue reaches you as the string codes. The booth has to stop and purge its nozzle whenever two bodies in a row ask for the same colour, so the shift lead wants the queue resequenced until no two neighbouring bodies share a code. You may put the bodies in any order you like, but you must send out exactly the bodies you were given, code for code.
Several orders usually avoid every purge, so build one specific order and return it: fill the queue from front to back, and at each slot send the code with the most bodies still waiting, skipping the code you placed in the slot before; when two or more codes have the same number of bodies waiting, send the one that comes earlier in the alphabet.
If no ordering can avoid a purge, return the empty string.
Examples
Example 1
- Input
- codes = "bbcbca"
- Output
- "bcbabc"
`b` starts with three bodies waiting, so it leads; then `c` with two beats `a` with one. At the fourth slot `a` and `c` each have one body left, and `a` wins the tie.
Example 2
- Input
- codes = "ccdc"
- Output
- ""
Three of the four bodies want `c`, and only one other body exists to separate them, so some pair of `c` bodies must end up adjacent.
Example 3
- Input
- codes = "ttssu"
- Output
- "ststu"
`s` and `t` both start with two bodies waiting, so the alphabet decides the first slot. The tie recurs at the third and fourth slots and is settled the same way, leaving the single `u` body last.
Constraints
- 1 <= codes.length <= 500
- codes consists of lowercase English letters
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def paint_line_shuffle(codes: str) -> str:public String paintLineShuffle(String codes)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's