1830. Minimum Number of Operations to Make String Sorted Hard

1/**
2 * [1830] Minimum Number of Operations to Make String Sorted
3 *
4 * You are given a string s (0-indexed)​​​​​​. You are asked to perform the following operation on s​​​​​​ until you get a sorted string:
5 * <ol>
6 * 	Find the largest index i such that 1 <= i < s.length and s[i] < s[i - 1].
7 * 	Find the largest index j such that i <= j < s.length and s[k] < s[i - 1] for all the possible values of k in the range [i, j] inclusive.
8 * 	Swap the two characters at indices i - 1​​​​ and j​​​​​.
9 * 	Reverse the suffix starting at index i​​​​​​.
10 * </ol>
11 * Return the number of operations needed to make the string sorted. Since the answer can be too large, return it modulo 10^9 + 7.
12 *  
13 * Example 1:
14 * 
15 * Input: s = "cba"
16 * Output: 5
17 * Explanation: The simulation goes as follows:
18 * 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".
19 * 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".
20 * 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".
21 * 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".
22 * 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".
23 * 
24 * Example 2:
25 * 
26 * Input: s = "aabaa"
27 * Output: 2
28 * Explanation: The simulation goes as follows:
29 * 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".
30 * 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".
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= s.length <= 3000
36 * 	s​​​​​​ consists only of lowercase English letters.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
42// discuss: https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn make_string_sorted(s: String) -> i32 {
48        0
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_1830() {
60    }
61}
62