Watch 7 video solutions for Minimum Number of Operations to Make String Sorted, a hard level problem involving Math, String, Combinatorics. This walkthrough by Happy Coding has 1,545 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s (0-indexed). You are asked to perform the following operation on s until you get a sorted string:
i such that 1 <= i < s.length and s[i] < s[i - 1].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.i - 1 and j.i.Return the number of operations needed to make the string sorted. Since the answer can be too large, return it 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".
Constraints:
1 <= s.length <= 3000s consists only of lowercase English letters.Problem Overview: You are given a string and an operation that transforms it into the previous lexicographical permutation. The task is to count how many operations are required until the string becomes fully sorted in ascending order.
Approach 1: Next/Previous Permutation Simulation (Potentially O(k * n) time, O(1) space)
The operation described in the problem is identical to generating the previous lexicographical permutation. One straightforward idea is to repeatedly apply a permutation routine similar to prev_permutation. Each step finds the rightmost index i where s[i] > s[i+1], swaps it with the largest smaller element to its right, then reverses the suffix. Continue until the string becomes fully sorted. This mirrors the standard permutation algorithm used in many libraries. The problem is that the number of permutations can be extremely large (up to factorial scale), so direct simulation quickly becomes infeasible for long strings.
Approach 2: Permutations Counting with Combinatorics (O(n^2) time, O(n) space)
The key observation: each operation moves the string one step backward in lexicographic order. Instead of simulating permutations, compute how many permutations are lexicographically smaller than the current string. That count equals the number of operations required.
Process the string from left to right. For each index i, count how many characters smaller than s[i] appear to the right. If you place one of those smaller characters at position i, the remaining suffix can be arranged in (n-i-1)! permutations. Because duplicate characters may exist, divide by factorials of character frequencies using modular inverses. Maintain frequency counts while iterating so you can adjust permutation counts dynamically. This approach relies heavily on combinatorics and factorial precomputation under modulo arithmetic.
The algorithm effectively computes the lexicographic rank of the string among all permutations of its multiset. Precompute factorials and modular inverses, maintain character counts, and accumulate contributions for each position. The string length can reach thousands, so this mathematical counting avoids factorial-scale enumeration.
Recommended for interviews: The combinatorics permutation-counting approach is the expected solution. Simulating permutations demonstrates understanding of lexicographic permutation mechanics, but the counting method shows deeper knowledge of math, combinatorics, and efficient handling of duplicate characters in string permutations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Next/Previous Permutation Simulation | O(k * n) | O(1) | Conceptual understanding of the operation or when the permutation count is very small |
| Combinatorics Permutation Counting | O(n^2) | O(n) | General case with large strings; computes lexicographic rank without enumerating permutations |