Welcome to Subscribe On Youtube
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
isuch that1 <= i < s.lengthands[i] < s[i - 1]. - Find the largest index
jsuch thati <= j < s.lengthands[k] < s[i - 1]for all the possible values ofkin 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 <= 3000s 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.
-
class Solution { private static final int N = 3010; private static final int MOD = (int) 1e9 + 7; private static final long[] f = new long[N]; private static final long[] g = new long[N]; static { f[0] = 1; g[0] = 1; for (int i = 1; i < N; ++i) { f[i] = f[i - 1] * i % MOD; g[i] = qmi(f[i], MOD - 2); } } public static long qmi(long a, int k) { long res = 1; while (k != 0) { if ((k & 1) == 1) { res = res * a % MOD; } k >>= 1; a = a * a % MOD; } return res; } public int makeStringSorted(String s) { int[] cnt = new int[26]; int n = s.length(); for (int i = 0; i < n; ++i) { ++cnt[s.charAt(i) - 'a']; } long ans = 0; for (int i = 0; i < n; ++i) { int m = 0; for (int j = s.charAt(i) - 'a' - 1; j >= 0; --j) { m += cnt[j]; } long t = m * f[n - i - 1] % MOD; for (int v : cnt) { t = t * g[v] % MOD; } --cnt[s.charAt(i) - 'a']; ans = (ans + t + MOD) % MOD; } return (int) ans; } } -
const int N = 3010; const int MOD = 1e9 + 7; long f[N]; long g[N]; long qmi(long a, int k) { long res = 1; while (k != 0) { if ((k & 1) == 1) { res = res * a % MOD; } k >>= 1; a = a * a % MOD; } return res; } int init = []() { f[0] = g[0] = 1; for (int i = 1; i < N; ++i) { f[i] = f[i - 1] * i % MOD; g[i] = qmi(f[i], MOD - 2); } return 0; }(); class Solution { public: int makeStringSorted(string s) { int cnt[26]{}; for (char& c : s) { ++cnt[c - 'a']; } int n = s.size(); long ans = 0; for (int i = 0; i < n; ++i) { int m = 0; for (int j = s[i] - 'a' - 1; ~j; --j) { m += cnt[j]; } long t = m * f[n - i - 1] % MOD; for (int& v : cnt) { t = t * g[v] % MOD; } ans = (ans + t + MOD) % MOD; --cnt[s[i] - 'a']; } return ans; } }; -
n = 3010 mod = 10**9 + 7 f = [1] + [0] * n g = [1] + [0] * n for i in range(1, n): f[i] = f[i - 1] * i % mod g[i] = pow(f[i], mod - 2, mod) class Solution: def makeStringSorted(self, s: str) -> int: cnt = Counter(s) ans, n = 0, len(s) for i, c in enumerate(s): m = sum(v for a, v in cnt.items() if a < c) t = f[n - i - 1] * m for v in cnt.values(): t = t * g[v] % mod ans = (ans + t) % mod cnt[c] -= 1 if cnt[c] == 0: cnt.pop(c) return ans -
const n = 3010 const mod = 1e9 + 7 var f = make([]int, n) var g = make([]int, n) func qmi(a, k int) int { res := 1 for k != 0 { if k&1 == 1 { res = res * a % mod } k >>= 1 a = a * a % mod } return res } func init() { f[0], g[0] = 1, 1 for i := 1; i < n; i++ { f[i] = f[i-1] * i % mod g[i] = qmi(f[i], mod-2) } } func makeStringSorted(s string) (ans int) { cnt := [26]int{} for _, c := range s { cnt[c-'a']++ } for i, c := range s { m := 0 for j := int(c-'a') - 1; j >= 0; j-- { m += cnt[j] } t := m * f[len(s)-i-1] % mod for _, v := range cnt { t = t * g[v] % mod } ans = (ans + t + mod) % mod cnt[c-'a']-- } return }