3863. Minimum Operations to Sort a String Medium

1/**
2 * [3863] Minimum Operations to Sort a String
3 *
4 * <p data-end="244" data-start="156">You are given a string s consisting of lowercase English letters.
5 * In one operation, you can select any <span data-keyword="substring-nonempty">substring</span> of s that is not the entire string and sort it in non-descending alphabetical order.
6 * Return the minimum number of operations required to make s sorted in non-descending order. If it is not possible, return -1.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">s = "dog"</span>
11 * Output: <span class="example-io">1</span>
12 * Explanation:​​​​​​​
13 * 
14 * 	Sort substring "og" to "go".
15 * 	Now, s = "dgo", which is sorted in ascending order. Thus, the answer is 1.
16 * </div>
17 * <strong class="example">Example 2:
18 * <div class="example-block">
19 * Input: <span class="example-io">s = "card"</span>
20 * Output: <span class="example-io">2</span>
21 * Explanation:
22 * 
23 * 	Sort substring "car" to "acr", so s = "acrd".
24 * 	Sort substring "rd" to "dr", making s = "acdr", which is sorted in ascending order. Thus, the answer is 2.
25 * </div>
26 * <strong class="example">Example 3:
27 * <div class="example-block">
28 * Input: <span class="example-io">s = "gf"</span>
29 * Output: <span class="example-io">-1</span>
30 * Explanation:
31 * 
32 * 	It is impossible to sort s under the given constraints. Thus, the answer is -1.
33 * </div>
34 *  
35 * Constraints:
36 * 
37 * 	1 <= s.length <= 10^5
38 * 	s consists of only lowercase English letters.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/minimum-operations-to-sort-a-string/
44// discuss: https://leetcode.com/problems/minimum-operations-to-sort-a-string/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn min_operations(s: String) -> i32 {
50        0
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_3863() {
62    }
63}
64