Formatted question description: https://leetcode.ca/all/1830.html
1830. Minimum Number of Operations to Make String Sorted
Level
Hard
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 10^9 + 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”.
Example 3:
Input: s = “cdbea”
Output: 63
Example 4:
Input: s = “leetcodeleetcodeleetcode”
Output: 982157772
Constraints:
1 <= s.length <= 3000
s
consists only of lowercase English letters.
Solution
This problem is to find the index of s
in the lexicographical order of all permutations of s
.
The solution is to count the number of permutations that are lexicographically smaller than s
.
class Solution {
static final int MODULO = 1000000007;
public int makeStringSorted(String s) {
int length = s.length();
int[] f = new int[26];
int[] p = new int[length + 1];
int[] all = new int[length + 1];
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
f[c - 'a']++;
}
p[1] = 1;
all[1] = 1;
for (int i = 2; i <= length; i++) {
int temp = power(i, MODULO - 2);
p[i] = (int) ((long) p[i - 1] * temp % MODULO);
all[i] = (int) ((long) all[i - 1] * i % MODULO);
}
int operations = 0;
for (int i = 0; i < length; i++) {
int left = length - 1 - i;
int index = s.charAt(i) - 'a';
for (int j = 0; j < index; j++) {
int up = all[left];
if (f[j] != 0) {
f[j]--;
for (int k = 0; k < 26; k++) {
if (f[k] != 0)
up = (int) ((long) up * p[f[k]] % MODULO);
}
operations = (operations + up) % MODULO;
f[j]++;
}
}
f[index]--;
}
return operations;
}
public int power(int x, int n) {
int power = 1;
while (n > 0) {
if (n % 2 == 1)
power = (int) ((long) power * x % MODULO);
x = (int) ((long) x * x % MODULO);
n /= 2;
}
return power;
}
}