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.
This approach involves calculating how many permutations of the string are lexicographically smaller than the given string. For each character in the string, calculate its contribution to make the string sorted using factorial number system representation. This provides the minimum number of operations required to make the string sorted.
This solution calculates the contribution of each character in the string to the number of permutations that are lexicographically smaller than the current string. It uses factorial arrays to efficiently calculate permutations and counts of letters for character contribution. The overall result gives the minimum number of operations needed based on permutation calculations.
Python
JavaScript
Time Complexity: O(n^2), where n is the length of the string, due to nested loops for character calculations.
Space Complexity: O(1) for constant space usage if we consider space for factorials as negligible for large n due to modular operations.
This approach uses the concept of finding the next lexicographical permutation to trace the number of operations needed to sort the string. By finding and applying the next permutation operation, we can simulate reaching the sorted order and count the operations needed. Each operation corresponds to a lexical improvement of the string.
This C++ solution calculates necessary operations to reach the sorted string using permutation calculations complemented with modular arithmetic. The pow_mod function helps handle modular inverses required in calculations. Counts of smaller lexicographical permutations lead to the required number of operations.
Time Complexity: O(n^2), where n is the string length, for calculating permutations and contributions.
Space Complexity: O(1) due to fixed auxiliary arrays beyond input space.
The operation in the problem is actually to find the previous permutation in lexicographical order of the current permutation. Therefore, we only need to find the number of permutations smaller than the current permutation, which is the answer.
Here we need to consider a problem: given the frequency of each letter, how many different permutations can we construct?
Suppose there are a total of n letters, among which there are n_1 letters a, n_2 letters b, and n_3 letters c. Then we can construct \frac{n!}{n_1! times n_2! times n_3!} different permutations. Where n=n_1+n_2+n_3.
We can pre-calculate all factorials f and the inverse of the factorials g through preprocessing. The inverse of the factorial can be obtained through Fermat's little theorem.
Next, we traverse the string s from left to right. For each position i, we need to find out how many letters are smaller than s[i], denoted as m. Then, we can construct m times \frac{(n - i - 1)!}{n_1! times n_2! cdots times n_k!} different permutations, where k is the number of types of letters, and add them to the answer. Next, we reduce the frequency of s[i] by one and continue to traverse the next position.
After traversing the entire string, we can get the answer. Note the modulo operation of the answer.
The time complexity is O(n times k), and the space complexity is O(n). Where n and k are the length of the string and the number of types of letters, respectively.
| Approach | Complexity |
|---|---|
| Permutations Counting Approach | Time Complexity: O(n^2), where n is the length of the string, due to nested loops for character calculations. |
| Next Permutation Approach | Time Complexity: O(n^2), where n is the string length, for calculating permutations and contributions. |
| Counting + Permutation and Combination + Preprocessing | — |
| 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 |
LeetCode 1830. Minimum Number of Operations to Make String Sorted • Happy Coding • 1,545 views views
Watch 6 more video solutions →Practice Minimum Number of Operations to Make String Sorted with our built-in code editor and test cases.
Practice on FleetCode