{x}
blog image

Minimum Number of Operations to Make String Sorted

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 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 <= 3000
  • s​​​​​​ consists only of lowercase English letters.

Solution Explanation: Minimum Number of Operations to Make String Sorted

This problem asks for the minimum number of operations to sort a given string lexicographically. Instead of simulating the operations, a more efficient approach leverages combinatorics. The core idea is that each operation essentially finds the next lexicographically smaller permutation of the string. Therefore, the solution boils down to calculating the number of permutations lexicographically smaller than the input string.

Algorithm:

  1. Preprocessing: Calculate factorials (f) and their modular inverses (g) up to a sufficiently large number (3010 in this case, considering the constraint on string length). The modular inverse is necessary for efficient modulo division in the context of modular arithmetic (we use Fermat's Little Theorem for this).

  2. Counting Inversions: Iterate through the input string s. For each character s[i], count the number of characters (m) that are smaller than s[i] and appear after s[i] in the string. This m represents how many permutations can be formed by swapping s[i] with one of those smaller characters and then reversing the suffix.

  3. Calculating Permutations: For each s[i], the number of permutations achievable by swapping s[i] with a smaller character is given by: m * ( (n - i - 1)! / (n1! * n2! * ... * nk!) ). Where:

    • n is the length of the string.
    • i is the current index.
    • (n - i - 1)! is the factorial of the remaining characters after s[i].
    • n1!, n2!, ..., nk! are the factorials of the counts of each unique character remaining after s[i].

  4. Accumulation: Sum the number of permutations calculated in step 3 for each character. This sum represents the total number of lexicographically smaller permutations, and thus, the minimum number of operations required. Remember to perform modulo operations at each step to prevent integer overflow.

Time Complexity: O(n * k), where n is the length of the string, and k is the number of unique characters (at most 26). The preprocessing of factorials takes O(n) time. The main loop iterates through the string once, and in each iteration, counting smaller characters and calculating permutations takes O(k) time.

Space Complexity: O(n), dominated by the storage of factorials and character counts.

Code Explanation (Python):

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) # Modular inverse using Fermat's Little Theorem
 
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

The other languages (Java, C++, Go) follow a very similar structure, differing mainly in syntax and handling of modular arithmetic. The core logic remains consistent across all implementations.