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:

1. Find the largest index i such that 1 <= i < s.length and s[i] < s[i - 1].
2. Find the largest index j such that i <= j < s.length and s[k] < s[i - 1] for all the possible values of k in the range [i, j] inclusive.
3. Swap the two characters at indices i - 1 and j.
4. 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.

• Java
• C++
• Python

• 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;
      }
  }
  

• // 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;
      }
  };
  

• print("Todo!")
  

All Problems

All Solutions