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.This problem asks for the number of operations required to transform a string into its sorted order using a specific operation equivalent to generating the previous permutation. Instead of simulating each step (which would be inefficient), the key idea is to compute the lexicographic rank of the string among all permutations of its characters.
Traverse the string from left to right. For each position, count how many characters smaller than the current character appear to the right. Each such choice represents permutations that would appear before the current arrangement. Using combinatorics, calculate how many permutations can be formed with the remaining characters. Because characters may repeat, divide by factorials of duplicate counts.
Efficient implementation requires precomputing factorials and modular inverses to handle large values under modulo arithmetic. Frequency arrays help track remaining characters. This transforms the problem into counting permutations rather than enumerating them.
The overall complexity is O(n * alphabet) or close to O(n) for typical lowercase constraints, with linear auxiliary storage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Combinatorics with Lexicographic Rank (factorials + frequency counting) | O(n * 26) ≈ O(n) | O(n) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
Note that the operations given describe getting the previous permutation of s
To solve this problem you need to solve every suffix separately
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of permutation ranking and combinatorics-based counting problems appear in FAANG and other top tech interviews. They test understanding of lexicographic order, factorial math, modular arithmetic, and handling duplicate characters efficiently.
Combinatorics helps count how many permutations are lexicographically smaller than the given string. Since the allowed operation effectively generates the previous permutation, the number of required operations equals the number of permutations before the current one.
A frequency array for characters is typically used to track remaining letters while iterating through the string. Precomputed factorial and modular inverse arrays are also important to efficiently calculate permutation counts with duplicate characters.
The optimal approach uses combinatorics to compute the lexicographic rank of the given string among all permutations of its characters. Instead of simulating operations, it counts how many permutations would appear before the string using factorials and frequency counts. Modular arithmetic is used to keep results within limits.