Minimum Number of Operations to Make String Sorted

You are given a string s of lowercase English letters. In each operation, you find the largest index i such that s[i] is not the last character in sorted order among s[i], s[i+1], ..., s[n-1], then find the largest index j where j > i and s[j] < s[i], swap s[i] and s[j], and reverse the suffix after position i. The task is to count the total number of operations needed to sort the string.

This is LeetCode 1830: Minimum Number of Operations to Make String Sorted. If the operation sounds familiar, it should. It is exactly the "previous permutation" operation. The answer is the number of times you can step backward through the permutation sequence before reaching the sorted string. In other words, it is the rank of the given string among all permutations of its characters.

Why this problem matters

Permutation ranking is a foundational concept in combinatorics and shows up in many forms across competitive programming and technical interviews. Understanding how to compute the rank of a permutation teaches you to combine factorial counting, character frequency tracking, and modular arithmetic into a single cohesive solution. These building blocks transfer directly to problems involving counting arrangements, computing combinatorial indices, and working with large numbers under modular constraints.

The key insight

Each operation is one step of the "previous permutation" algorithm. The total number of operations equals the number of permutations that are lexicographically smaller than s. This transforms the problem from simulation into a pure math question: what is the rank of s among all permutations of its characters?

To compute the rank, process the string from left to right. At each position i, count how many characters in the remaining suffix are smaller than s[i]. Each such character could have been placed at position i to form a lexicographically smaller permutation. The number of distinct permutations you can form with the remaining characters (with one of those smaller characters fixed at position i) is the multinomial coefficient of the remaining suffix. Sum these contributions for all positions to get the total rank.

Because the string can have duplicate characters, you need the multinomial formula: (n-1)! / (c1! * c2! * ... * c26!) where the c values are the counts of each remaining character. Since the answer can be huge, all arithmetic is done modulo 10^9 + 7, which means you need modular inverses for the factorial divisions.

The solution

class Solution:
    def makeStringSorted(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)

        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i % MOD

        inv_fact = [1] * (n + 1)
        inv_fact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1):
            inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

        count = [0] * 26
        result = 0

        for i in range(n - 1, -1, -1):
            c = ord(s[i]) - ord('a')
            count[c] += 1
            smaller = sum(count[:c])
            suffix_len = n - i - 1

            contrib = smaller * fact[suffix_len] % MOD
            for j in range(26):
                contrib = contrib * inv_fact[count[j]] % MOD

            result = (result + contrib) % MOD

        return result

The solution starts by precomputing factorials and their modular inverses up to n. This lets you compute any multinomial coefficient in O(26) time. Then it processes the string from right to left, maintaining a frequency array count of characters seen so far in the suffix. At each position, it counts how many characters in the suffix are smaller than the current character. The contribution from this position is smaller * (suffix_len)! / (c1! * c2! * ... * c26!), computed using the precomputed inverse factorials.

Visual walkthrough

Here is the algorithm applied to the string "cba", computing the rank step by step.

The final answer of 5 matches what you would find by listing all 6 permutations of "cba" in sorted order and counting those that come before it: "abc", "acb", "bac", "bca", "cab" are all lexicographically smaller.

Complexity analysis

The time complexity is O(n * 26) because for each of the n positions, you iterate over 26 possible characters to compute the multinomial denominator and count smaller characters. The factorial and inverse factorial precomputation takes O(n) time. The space complexity is O(n) for the factorial arrays, plus O(26) for the character frequency array.

The building blocks

1. Factorial precomputation with modular inverse

To divide by factorials under a modulus, you need modular multiplicative inverses. Since 10^9 + 7 is prime, you can compute the inverse of x as pow(x, MOD - 2, MOD) using Fermat's little theorem. Precomputing all inverse factorials takes O(n) time using the identity inv_fact[i] = inv_fact[i+1] * (i+1).

fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i % MOD

inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

2. Multinomial coefficient for permutations with duplicates

When characters repeat, the number of distinct permutations of a multiset is n! / (c1! * c2! * ... * ck!). This is the multinomial coefficient. Using precomputed inverse factorials, you can evaluate this in O(26) time by multiplying fact[n] by each inv_fact[count[j]].

contrib = smaller * fact[suffix_len] % MOD
for j in range(26):
    contrib = contrib * inv_fact[count[j]] % MOD

3. Permutation ranking via positional contributions

The rank of a permutation is computed by summing contributions from each position. At position i, you count how many characters in the remaining suffix are strictly smaller than s[i]. Each such character, if placed at position i, would produce a lexicographically smaller string. The number of ways to arrange the rest of the suffix gives the contribution for that position.

smaller = sum(count[:c])

Edge cases

• Already sorted string. The rank of a sorted permutation is 0, so the answer is 0. No characters at any position have smaller characters to their right.
• All identical characters. There is only one distinct permutation, so the rank is always 0.
• Single character. The string is trivially sorted. The answer is 0.
• String of length 3000 (maximum constraint). The factorial precomputation and modular inverse approach handle this efficiently within O(n * 26) time.
• String with all 26 distinct letters. The multinomial coefficient reduces to a plain factorial since all counts are 1. The formula still works correctly.

From understanding to recall

The tricky part of this problem is not the code itself but the mental model connecting "previous permutation operations" to "permutation ranking." Once you see that each operation steps backward through the lexicographic sequence, the counting formula follows naturally. But that connection is easy to forget under pressure.

When you review this problem, focus on two things: recognizing that repeated application of the previous permutation equals computing a rank, and remembering how to handle duplicate characters with the multinomial coefficient. Spaced repetition helps you internalize both the pattern recognition and the formula mechanics, so they become second nature when you encounter similar problems.

Related posts

• Orderly Queue - Another string permutation problem that requires mathematical insight
• Next Permutation - The fundamental algorithm for generating the next lexicographic permutation
• Permutations - Generating all permutations using backtracking

Permutation ranking, modular arithmetic, and multinomial coefficients are patterns that appear across many hard problems. Building fluency with these tools makes a whole category of combinatorics problems approachable. CodeBricks helps you drill these concepts with spaced repetition so the formulas and insights stay fresh when you need them.