#1830
Minimum Number of Operations to Make String Sorted
candidate master · 1445 · lc hard +32 · verified · 50.8% accepted · 188 likes · top 39%
Description
Given a 0-indexed string s, apply the following operation repeatedly until s is fully sorted:
- Find the largest index i with 1 <= i < s.length where s[i] < s[i - 1].
- Find the largest index j with i <= j < s.length such that s[k] < s[i - 1] for every k in the range [i, j].
- Swap s[i - 1] with s[j].
- Reverse the suffix of s starting at index i.
Return the total number of operations taken, modulo 109 + 7.
Example 1:
Input: s = "cba"
Output: 5
Explanation: The simulation goes as follows:
Operation 1: i=2, j=2. Swap s[1] and s[2] to get s="cab", then reverse the suffix starting at 2. Now, s="cab".
Operation 2: i=1, j=2. Swap s[0] and s[2] to get s="bac", then reverse the suffix starting at 1. Now, s="bca".
Operation 3: i=2, j=2. Swap s[1] and s[2] to get s="bac", then reverse the suffix starting at 2. Now, s="bac".
Operation 4: i=1, j=1. Swap s[0] and s[1] to get s="abc", then reverse the suffix starting at 1. Now, s="acb".
Operation 5: i=2, j=2. Swap s[1] and s[2] to get s="abc", then reverse the suffix starting at 2. Now, s="abc".
Example 2:
Input: s = "aabaa"
Output: 2
Explanation: The simulation goes as follows:
Operation 1: i=3, j=4. Swap s[2] and s[4] to get s="aaaab", then reverse the substring starting at 3. Now, s="aaaba".
Operation 2: i=4, j=4. Swap s[3] and s[4] to get s="aaaab", then reverse the substring starting at 4. Now, s="aaaab".
Code
1
2
3