#1830

Hard

LeetCode Problem Workspace

Minimum Number of Operations to Make String Sorted

Calculate the minimum operations to sort a string using combinatorial math and string manipulation techniques efficiently.

math string combinatorics

Problem Statement

You are given a 0-indexed string s consisting of lowercase English letters. You must repeatedly perform the following operation: find the largest index i such that s[i] > s[i+1], then find the largest index j > i such that s[i] > s[j], swap s[i] and s[j], and reverse the substring from i+1 to the end.

Return the total number of operations needed to make the string sorted in non-decreasing order. Because the answer may be very large, return it modulo 1000000007. For example, s = "cba" requires 5 operations to reach "abc".

Examples

Example 1

Input: s = "cba"

Output: 5

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

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 Approach

Combinatorial Rank Calculation

Compute the lexicographical rank of the string using factorials and counts of remaining characters. Each character contributes a number of permutations that start with a smaller character, which sums to the total operations.

Modulo Factorials for Large Strings

Precompute factorials and modular inverses to efficiently handle repeated calculations of permutations. This avoids simulating each swap, which is crucial for strings up to length 3000.

Iterate with Character Counts

Track the frequency of each character while iterating from left to right. For each character, calculate how many permutations exist with smaller characters on its position and accumulate the total under modulo arithmetic.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n*26) due to iterating through the string and checking counts of smaller characters. Space complexity is O(n + 26) for factorials, inverses, and character counts.

What Interviewers Usually Probe

Expect efficient combinatorial counting rather than naive simulation.
Watch for modulo arithmetic to prevent overflow with large n.
Clarify handling of repeated characters in the string.

Common Pitfalls or Variants

Common pitfalls

Simulating every operation leads to timeouts for large strings.
Ignoring repeated characters can give incorrect operation counts.
Forgetting to apply modulo 10^9+7 results in overflow errors.

Follow-up variants

Calculate the minimum operations to sort a string using only swaps without reversals.
Determine the lexicographical rank of the string among all permutations.
Count operations when only adjacent swaps are allowed.

FAQ

What is the main strategy to solve Minimum Number of Operations to Make String Sorted?

Use combinatorial counting of permutations with factorials and modular arithmetic rather than simulating each swap.

Why do we need modulo 10^9+7?

Because the number of operations can be extremely large, modulo prevents integer overflow.

How do repeated characters affect the solution?

Repeated characters reduce the number of unique permutations, so frequency counts must be applied in factorial divisions.

Is simulating swaps a feasible approach?

No, direct simulation is too slow for strings up to 3000 characters; combinatorial counting is required.

Which patterns does this problem focus on?

It focuses on Math plus String, combining combinatorial ranking with string manipulation logic.

terminal

Solution

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

Continue Practicing

#2063 vowels of all substrings #2514 count anagrams #2842 count k subsequences of a string with maximum beauty