A library return cart holds n books lined up in a row, each labeled with a single lowercase genre code letter ('a' to 'z') in the order they were dropped off. A librarian repeatedly performs the following operation: pick any one book currently on the cart, lift it out, and place it at the very end of the row (after every book still on the cart). After some number of such operations, the row of genre codes should read in non-decreasing order from front to back (each letter is alphabetically the same as, or later than, the one directly before it). Find the minimum number of operations needed to achieve this.
n — the number of books.n lowercase English letters — the genre codes from front to back of the row.A single integer: the minimum number of operations needed to make the row non-decreasing.
'a'-'z'.Example 1
Input
3 bac
Expected
2
Explanation
Start: b, a, c. The sorted target is a, b, c. Scanning for 'a' after the start finds it at position 2, but nothing after it in the row is 'b' -- so only the single book 'a' can stay untouched. Moving 'b' to the end gives a, c, b; then moving 'c' to the end gives a, b, c -- sorted in exactly 2 operations. One operation is never enough, since no matching of two consecutive target letters (a then b, in that left-to-right order) exists in the original row.
Example 2
Input
5 cbdae
Expected
4
Explanation
Start: c, b, d, a, e. The sorted target is a, b, c, d, e. Scanning for 'a' finds it at position 4, but no 'b' appears anywhere after it, so only the book 'a' can stay untouched (matched length 1). Moving the remaining books to the end in the order b, then c, then d, then e produces c,d,a,e,b -> d,a,e,b,c -> a,e,b,c,d -> a,b,c,d,e, sorted after exactly 4 operations, and no shorter sequence of moves achieves a sorted row.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →