1830. Minimum Number of Operations to Make String Sorted
Description
You are given a string s
(0-indexed)ββββββ. You are asked to perform the following operation on s
ββββββ until you get a sorted string:
- Find the largest index
i
such that1 <= i < s.length
ands[i] < s[i - 1]
. - Find the largest index
j
such thati <= j < s.length
ands[k] < s[i - 1]
for all the possible values ofk
in the range[i, j]
inclusive. - Swap the two characters at indices
i - 1
ββββ andj
βββββ. - Reverse the suffix starting at index
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 <= 3000
s
ββββββ consists only of lowercase English letters.
Solutions
Solution 1: Counting + Permutation and Combination + Preprocessing
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
|