Minimum Operations to Sort a String
Real-world version: Fewest Lifts to Order the Bead StringThe statement here is our own: the same inputs, outputs and technique.
A string of beads is given as s, each bead marked with a lowercase letter.
One lift takes a single bead off the string and threads it back on at any position, including either end. The other beads keep their order.
The string is ordered when its letters read in non-decreasing order from one end to the other. Return the fewest lifts that leave it ordered.
Examples
Example 1
- Input
- s = "cba"
- Output
- 2
Leaving the bead marked "a" alone and lifting the other two, threading "b" after it and then "c" after that, orders the string in two lifts.
Example 2
- Input
- s = "abab"
- Output
- 1
The beads reading "a", "a" and "b" can be left alone as a non-decreasing run, so only the remaining bead has to be lifted.
Example 3
- Input
- s = "aabbcc"
- Output
- 0
The string already reads in non-decreasing order, so no bead has to move.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters only
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 fewest_lifts(s: str) -> int:public int fewestLifts(String s)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