Mid/SeniorString
Minimum Operations to Sort a String
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
1Sort substring
"og" to "go", making s = "dgo", which is sorted in ascending order, so the answer is 1.Example 2
Input
s = "card"Output
2Sort substring
"car" to "acr" to get s = "acrd", then sort substring "rd" to "dr", making s = "acdr", so the answer is 2.Constraints
- 1 <= s.length <= 10^5
- s consists of only lowercase English letters.