1830. Minimum Number of Operations to Make String Sorted¶

• Time: $O(26n) = O(n)$
• Space: $O(n)$
  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 class Solution { public: int makeStringSorted(string s) { const int n = s.length(); const auto [fact, invFact] = getFactAndInvFact(n); int ans = 0; vector count(26); for (int i = n - 1; i >= 0; --i) { const int order = s[i] - 'a'; ++count[order]; long perm = accumulate(count.begin(), count.begin() + order, 0) * fact[n - 1 - i] % kMod; for (int j = 0; j < 26; ++j) perm = perm * invFact[count[j]] % kMod; ans = (ans + perm) % kMod; } return ans; } private: static constexpr int kMod = 1'000'000'007; pair, vector> getFactAndInvFact(int n) { vector fact(n + 1); vector invFact(n + 1); vector inv(n + 1); fact[0] = invFact[0] = 1; inv[0] = inv[1] = 1; for (int i = 1; i <= n; ++i) { if (i >= 2) inv[i] = kMod - kMod / i * inv[kMod % i] % kMod; fact[i] = fact[i - 1] * i % kMod; invFact[i] = invFact[i - 1] * inv[i] % kMod; } return {fact, invFact}; } }; 
  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 class Solution { public int makeStringSorted(String s) { final int kMod = 1_000_000_007; final int n = s.length(); final long[][] factAndInvFact = getFactAndInvFact(n); final long[] fact = factAndInvFact[0]; final long[] invFact = factAndInvFact[1]; int ans = 0; int[] count = new int[26]; for (int i = n - 1; i >= 0; --i) { final int order = s.charAt(i) - 'a'; ++count[order]; long perm = Arrays.stream(count, 0, order).sum() * fact[n - 1 - i] % kMod; for (int j = 0; j < 26; ++j) perm = perm * invFact[count[j]] % kMod; ans += perm; ans %= kMod; } return ans; } private static final int kMod = 1_000_000_007; private long[][] getFactAndInvFact(int n) { long[] fact = new long[n + 1]; long[] invFact = new long[n + 1]; long[] inv = new long[n + 1]; fact[0] = invFact[0] = 1; inv[0] = inv[1] = 1; for (int i = 1; i <= n; ++i) { if (i >= 2) inv[i] = kMod - kMod / i * inv[kMod % i] % kMod; fact[i] = fact[i - 1] * i % kMod; invFact[i] = invFact[i - 1] * inv[i] % kMod; } return new long[][] {fact, invFact}; } } 
  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 class Solution: def makeStringSorted(self, s: str) -> int: kMod = 1_000_000_007 ans = 0 count = [0] * 26 @functools.lru_cache(None) def fact(i: int) -> int: return 1 if i <= 1 else i * fact(i - 1) % kMod @functools.lru_cache(None) def inv(i: int) -> int: return pow(i, kMod - 2, kMod) for i, c in enumerate(reversed(s)): order = string.ascii_lowercase.index(c) count[order] += 1 # count[:order] := s[i] can be any character smaller than c # fact(i) := s[i + 1..n - 1] can be any sequence of characters perm = sum(count[:order]) * fact(i) for j in range(26): perm = perm * inv(fact(count[j])) % kMod ans = (ans + perm) % kMod return ans