Welcome to Subscribe On Youtube
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
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 - 1andj. - 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 <= 3000sconsists 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; } } ############ 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; } } -
// OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/ // Time: O(NM * log(MOD)) // Space: O(N) class Solution { long modpow(long base, long exp, long mod) { long ans = 1; while (exp) { if (exp & 1) ans = (ans * base) % mod; base = (base * base) % mod; exp >>= 1; } return ans; } public: int makeStringSorted(string s) { long N = s.size(), cnt[26] = {}, mod = 1e9 + 7, ans = 0; vector<long> fact(N + 1, 1); for (int i = 1; i <= N; ++i) fact[i] = (fact[i - 1] * i) % mod; for (int i = N - 1; i >= 0; --i) { ++cnt[s[i] - 'a']; long less = 0, div = 1; for (int j = 0; j < 26; ++j) { if (j < s[i] - 'a') less += cnt[j]; div = (div * fact[cnt[j]]) % mod; } ans = (ans + less * fact[N - i - 1] % mod * modpow(div, mod - 2, mod) % mod) % mod; } 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 }