Loading problem…
You are given a string s consisting of lowercase English letters. In one operation, you can select any substring of s that is not the entire string and sort it in non-descending alphabetical order. Return the minimum number of operations required to make s sorted in non-descending order. If it is not possible, return -1.
Example 1
Input: s = dog
Output: 1
Explanation: Sort the substring "og" into "go" and s becomes "dgo", which is sorted. The correct first letter 'd' was already in place, so one sort finishes the job.
Example 2
Input: s = card
Output: 2
Explanation: Both the first and last letters are out of place. Sort "car" into "acr" to get "acrd", then sort "rd" into "dr" to get "acdr". Two sorts are needed.
Example 3
Input: s = gf
Output: -1
Explanation: The only substrings that are not the whole string are the single letters 'g' and 'f', and sorting one letter changes nothing, so a length-two unsorted string can never be sorted.
The target is always sorted(s); compare s to it and look only at where they differ. If that difference window leaves a correct prefix or suffix in place, one sort fixes it; otherwise the two blocked endpoints decide between 2 and 3 operations.
Run checks all cases above. Submit evaluates all test cases.