Code Implementation

MOD = 10**9 + 7

class Solution:
    def makeStringSorted(self, s: str) -> int:
        from math import factorial

        n = len(s)
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1

        # Precompute factorials and inverse factorials
        fact = [1] * (n + 1)
        inv_fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i % MOD
        inv_fact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n, 0, -1):
            inv_fact[i - 1] = inv_fact[i] * i % MOD

        res = 0
        for i in range(n):
            curr = ord(s[i]) - ord('a')
            for j in range(curr):
                if freq[j] == 0:
                    continue
                freq[j] -= 1
                denom = 1
                for k in range(26):
                    denom = denom * inv_fact[freq[k]] % MOD
                count = fact[n - i - 1] * denom % MOD
                res = (res + count) % MOD
                freq[j] += 1
            freq[curr] -= 1
        return res
      

class Solution {
public:
    const int MOD = 1e9 + 7;

    long long modPow(long long x, long long n, long long mod) {
        long long res = 1;
        while (n) {
            if (n & 1) res = res * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }

    int makeStringSorted(string s) {
        int n = s.size();
        vector fact(n+1, 1), inv_fact(n+1, 1);

        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i-1] * i % MOD;
        inv_fact[n] = modPow(fact[n], MOD-2, MOD);
        for (int i = n; i > 0; --i)
            inv_fact[i-1] = inv_fact[i] * i % MOD;

        vector freq(26, 0);
        for (char c : s) freq[c - 'a']++;

        long long res = 0;
        for (int i = 0; i < n; ++i) {
            int curr = s[i] - 'a';
            for (int j = 0; j < curr; ++j) {
                if (freq[j] == 0) continue;
                freq[j]--;
                long long denom = 1;
                for (int k = 0; k < 26; ++k)
                    denom = denom * inv_fact[freq[k]] % MOD;
                long long count = fact[n - i - 1] * denom % MOD;
                res = (res + count) % MOD;
                freq[j]++;
            }
            freq[curr]--;
        }
        return (int)res;
    }
};
      

class Solution {
    static final int MOD = 1_000_000_007;

    public int makeStringSorted(String s) {
        int n = s.length();
        long[] fact = new long[n + 1];
        long[] invFact = new long[n + 1];
        fact[0] = invFact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        invFact[n] = pow(fact[n], MOD - 2, MOD);
        for (int i = n; i >= 1; i--) {
            invFact[i - 1] = invFact[i] * i % MOD;
        }
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            int curr = s.charAt(i) - 'a';
            for (int j = 0; j < curr; j++) {
                if (freq[j] == 0) continue;
                freq[j]--;
                long denom = 1;
                for (int k = 0; k < 26; k++) {
                    denom = denom * invFact[freq[k]] % MOD;
                }
                long count = fact[n - i - 1] * denom % MOD;
                res = (res + count) % MOD;
                freq[j]++;
            }
            freq[curr]--;
        }
        return (int) res;
    }

    private long pow(long x, long n, long mod) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1) res = res * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }
}
      

var makeStringSorted = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const fact = new Array(n + 1).fill(1);
    const invFact = new Array(n + 1).fill(1);

    for (let i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    invFact[n] = pow(fact[n], MOD - 2, MOD);
    for (let i = n; i > 0; i--) {
        invFact[i - 1] = invFact[i] * i % MOD;
    }

    const freq = new Array(26).fill(0);
    for (const c of s) {
        freq[c.charCodeAt(0) - 97]++;
    }

    let res = 0;
    for (let i = 0; i < n; i++) {
        const curr = s.charCodeAt(i) - 97;
        for (let j = 0; j < curr; j++) {
            if (freq[j] === 0) continue;
            freq[j]--;
            let denom = 1;
            for (let k = 0; k < 26; k++) {
                denom = denom * invFact[freq[k]] % MOD;
            }
            let count = fact[n - i - 1] * denom % MOD;
            res = (res + count) % MOD;
            freq[j]++;
        }
        freq[curr]--;
    }
    return res;

    function pow(x, n, mod) {
        let res = 1;
        x = x % mod;
        while (n > 0) {
            if (n % 2 === 1) res = res * x % mod;
            x = x * x % mod;
            n = Math.floor(n / 2);
        }
        return res;
    }
};
      

Problem Description

Given a string s, you can perform the following operation any number of times: pick any character in s and move it to the end of the string. Your task is to find the minimum number of such operations needed to make s sorted in lexicographical (dictionary) order.

Constraints:

• All characters in s are lowercase English letters.
• The answer can be large, so return it modulo 10^9 + 7.
• Each operation moves one existing character to the end; you cannot insert new characters or reuse characters.
• There is only one valid way to sort the string lexicographically.

Thought Process

At first glance, you might think of literally simulating the process: at each step, check if the string is sorted, and if not, move a character to the end. However, this approach is inefficient and doesn't scale for large strings.

Instead, we realize that the problem is closely related to finding the "rank" of the string among all its possible anagrams (permutations) sorted lexicographically. Each time you move a character to the end, you are effectively skipping over a lexicographically smaller permutation. Thus, the minimal number of moves is the number of permutations of s that are lexicographically smaller than the current s.

The challenge is to efficiently count, for each position, how many permutations can be formed by swapping the current character with a smaller character that appears later in the string, taking into account duplicate letters.

Solution Approach

The solution uses combinatorics to count the number of smaller permutations efficiently. Here’s how:

1. Precompute Factorials and Inverses:
   • We need to compute the number of unique permutations of the remaining characters, which involves factorials and division (to handle repeated letters).
   • Because division in modular arithmetic requires modular inverses, we precompute factorials and their modular inverses up to n (the length of s).
2. Frequency Count:
   • We maintain a frequency array freq for the 26 lowercase English letters to keep track of how many of each character remain.
3. Iterate Over the String:
   • For each character in s from left to right, for each character less than the current one (lexicographically), we consider "what if we put that smaller character here instead?"
   • We decrement the frequency of that smaller character and calculate the number of distinct permutations of the remaining characters. This is done by fact[remaining] divided by the product of fact[freq[letter]] for all letters (using modular inverses).
   • Sum up these counts for all such positions, then restore the frequency for the next iteration.
4. Update Frequencies:
   • After processing all smaller characters, decrement the frequency of the current character, as it is now "used up".
5. Return the Result:
   • After processing the entire string, the sum gives the number of moves needed to make s sorted.

This approach ensures that duplicate letters are handled correctly, and all arithmetic is performed modulo 10^9 + 7.

Example Walkthrough

Example: s = "cba"

1. Step 1 (i = 0, char = 'c'):
   • Characters less than 'c' are 'a' and 'b'.
   • Try placing 'a' at the first position: Remaining string is "b c" (after using one 'a'), which can be arranged in 2! = 2 ways.
   • Try placing 'b' at the first position: Remaining string is "a c", which can be arranged in 2! = 2 ways.
   • So, 2 (for 'a') + 2 (for 'b') = 4 permutations before the original "cba".
2. Step 2 (i = 1, char = 'b'):
   • Only 'a' is less than 'b'.
   • Try placing 'a' at this position: Remaining string is "c", which can be arranged in 1 way.
   • So, add 1.
3. Step 3 (i = 2, char = 'a'):
   • No character is less than 'a', so nothing to add.

Total: 4 (from step 1) + 1 (from step 2) = 5. So, 5 moves are needed to make "cba" sorted ("abc").

Time and Space Complexity

• Brute-force approach:
  • Would involve generating all permutations, which has time complexity O(n!), and is not feasible for large n.
• Optimized combinatorial approach:
  • Time complexity: O(n * 26), since for each character in the string (n), we check up to 26 possible smaller characters, and for each, we compute the denominator for permutations (which is O(26)).
  • Space complexity: O(n), mainly for storing factorials and inverse factorials up to n.

Summary

The key insight is to model the problem as finding the lexicographical rank of the string among all its permutations, which can be efficiently calculated using combinatorics and modular arithmetic. By precomputing factorials and their inverses, and carefully managing the frequency of each character, we can efficiently count how many permutations are smaller than the current string. This approach elegantly sidesteps brute-force simulation, providing a fast and scalable solution.