1830. Minimum Number of Operations to Make String Sorted


Problem Description

The given problem presents you with a string s, and you are required to repeatedly perform a sequence of operations to make the string sorted in lexicographical order (i.e., dictionary order). The operations are as follows:

  1. Identify the largest index i satisfying 1 <= i < s.length such that the character at s[i] is less than the character at s[i - 1].
  2. Find the largest index j greater than or equal to i such that every character at position k within the range [i, j] is less than the character at s[i - 1].
  3. Swap the characters at positions i - 1 and j.
  4. Reverse the string segment starting from index i.

The task is then to compute how many times you must perform this sequence of operations to sort the string. However, since the number of operations could be enormous, you are asked to return this number modulo 10^9 + 7.

Intuition

The intuition behind solving this problem lies in combinatorics and understanding that each operation is essentially a step towards placing the characters in the correct order.

The idea is to iterate through the string and calculate the number of operations needed to place each character in its sorted position by considering the permutations of characters remaining to be sorted.

This approach avoids actually performing the operations on the string, which would be inefficient, and instead counts the number of operations in a combinatorial way.

Here's a step-by-step breakdown of the solution intuition:

  1. Calculate factorial f and modulo multiplicative inverse g in advance for efficient computation during iteration.

  2. Use a counter to keep track of the number of occurrences of each character in the string.

  3. Iterate over the string:

    • Calculate the count, m, of characters less than the current character which have not already been placed correctly.

    • Determine the permutations t of the remaining characters, which would represent the number of possible strings if we were to place the current character in its correct sorted position now.

    • Adjust for the duplicate characters by multiplying with the modulo multiplicative inverse g[v] for each character count v.

    • Update the total count ans of operations needed, by adding t modulo 10^9 + 7.

    • Decrement the character count for the current character in the counter to reflect that this character has been placed in its correct position.

  4. The computed ans is returned which gives us the required number of operations modulo 10^9 + 7.

  5. This approach cleverly avoids actually performing the operations, which could be costly especially for long strings, by instead mathematically computing the number of steps needed to obtain the sorted string.

Solution Approach

The implementation of the solution makes use of several key concepts from combinatorics, as well as Python-specific data structures and functions to efficiently perform necessary calculations.

Here's a detailed walk-through:

  1. Pre-calculation of factorials (f) and their modulo multiplicative inverses (g):

    • Factorials of all possible index positions are precalculated and stored in an array f, using the modulo operation to avoid integer overflow.
    • The modulo multiplicative inverse of each factorial is calculated using pow(f[i], mod - 2, mod) due to Fermat's Little Theorem, allowing us to efficiently calculate division in modular arithmetic. These inverses are stored in the array g.

    This is a preprocessing step to speed up the calculations needed for each operation count later on.

  2. Using Counter to keep track of character frequencies:

    • A Counter from the collections module is utilized to count occurrences of each character in the string. This is particularly useful for calculating the multiplicative inverse part of the permutation calculation.
  3. Main algorithmic loop:

    • We loop over each character c in the string s with its index i. For each character, the goal is to find how many operations are needed to move it to its correct place given the characters that have yet to be ordered.

    • The variable m is the number of characters less than c that are currently placed to the right of their target position.

    • Compute the partial operations count t by multiplying the factorial f[n - i - 1] (representing the permutations of remaining characters) by the number m.

    • Adjust t to account for duplicate characters by multiplying it with the modulo multiplicative inverses of the counts of the remaining characters. This part is crucial because it handles the division in the permutations formula.

  4. Combination of counts and modular arithmetic:

    • Each partial count t is added to the total answer ans, with modulo 10^9 + 7 being applied at every step to manage large numbers and prevent overflow.
    • After processing a character, we decrement its count in the Counter to account for having effectively placed that character in its final sorted position.
  5. Final result:

    • Once the loop is done, the resulting ans variable holds the total count of operations needed to sort the string, modulo 10^9 + 7.

The use of the factorial array, multiplicative inverses, and Counter for frequency tracking together form a powerful combination that allows us to compute the total operation count efficiently without actually performing the swaps and reversals described in the problem statement.

Example Walkthrough

Let's consider an example with the string s = "bca" and walk through the solution approach.

  1. Pre-calculation of factorials (f) and their modulo multiplicative inverses (g):

    For a string of length 3, we would calculate factorials for 0, 1, 2, 3 and their inverses accordingly. Let's assume we have computed them as follows (using a modulus mod = 10^9 + 7):

    • f = [1, 1, 2, 6] (factorials modulo mod)
    • g = [1, 1, 500000004, 166666668] (inverses modulo mod)
  2. Using Counter to keep track of character frequencies:

    By counting the occurrences of each character, we get:

    • Counter = {'b': 1, 'c': 1, 'a': 1}
  3. Main algorithmic loop:

    Now, we iterate over the string:

    • For character b at index 0:

      • m is the count of characters less than b to its right, which is 1 ('a').
      • Calculate permutation count t as m * f[n - i - 1], which gives 1 * f[2]
      • Correct for any duplicates, which isn't necessary here as all counts are 1.
      • t is now 1 * 2 = 2.
      • Add t to the total operations count, ans += 2 % mod.
    • For character c at index 1:

      • m is the count of characters less than c to its right, which is 1 ('a').
      • Calculate permutation count t as m * f[n - i - 1], which gives 1 * f[1]
      • Correct for any duplicates, which again isn't needed.
      • t is 1 * 1 = 1.
      • Add t to the total operations count, ans += 1 % mod.
    • For the last character at index 2, no operation is needed as it's already in the last position, so m = 0.

  4. Combination of counts and modular arithmetic:

    • By summing the partial counts (while taking mod at each step):
      • ans = (0 + 2 + 1) % mod
      • ans = 3 % mod, which means 3 operations are required to sort "bca" into "abc".
  5. Final result:

    Thus, the total count of operations needed to sort the string "bca" into "abc" is 3, and considering the modulus, the answer remains 3, representing the result modulo 10^9 + 7.

Note that in a longer string, the factors and the multiplicative inverses would allow us to handle the calculations without actually having to perform the swaps and reverses as the string's sorting operations. The example uses small factorials and inverses for simplicity, and in practice, these would be precomputed for efficient computation in the main loop for larger strings.

Python Solution

1from collections import Counter
2from math import factorial
3
4# Constants for modular operations
5MOD = 10**9 + 7
6N = 3010
7
8# Precalculate factorials and their modular inverses up to N
9factorials = [1] * (N + 1)
10modular_inverses = [1] * (N + 1)
11for i in range(1, N + 1):
12    factorials[i] = factorials[i - 1] * i % MOD
13    modular_inverses[i] = pow(factorials[i], MOD - 2, MOD)  # Using Fermat's little theorem
14
15class Solution:
16    def makeStringSorted(self, s: str) -> int:
17        # Count the frequency of each character in the string
18        char_count = Counter(s)
19        # Initialize count of operations
20        operations_count = 0
21        # Length of the string
22        string_length = len(s)
23        # Iterate through each character
24        for index, char in enumerate(s):
25            # Calculate the rank of the current character in the remaining alphabet
26            rank = sum(count for current_char, count in char_count.items() if current_char < char)
27            # Calculate the number of permutations that start with a smaller character
28            permutations = factorials[string_length - index - 1] * rank
29            # Update permutations to account for duplicate characters
30            for count in char_count.values():
31                permutations = permutations * modular_inverses[count] % MOD
32            # Add the current permutations to the operations count
33            operations_count = (operations_count + permutations) % MOD
34            # Decrease the count of the current character
35            char_count[char] -= 1
36            # Remove the character from the counter if its count is zero
37            if char_count[char] == 0:
38                del char_count[char]
39        # Return the total count of operations needed to sort the string
40        return operations_count
41

Java Solution

1class Solution {
2    // Constants for the problem's scope and modulo operation
3    private static final int MAX_LENGTH = 3010;
4    private static final int MOD = (int) 1e9 + 7;
5  
6    // Arrays to store factorial and their modular inverses
7    private static final long[] factorial = new long[MAX_LENGTH];
8    private static final long[] inverseFactorial = new long[MAX_LENGTH];
9
10    // Static block to initialize the factorial and inverseFactorial arrays
11    static {
12        factorial[0] = 1;
13        inverseFactorial[0] = 1;
14        for (int i = 1; i < MAX_LENGTH; ++i) {
15            factorial[i] = factorial[i - 1] * i % MOD;
16            inverseFactorial[i] = quickModularInverse(factorial[i], MOD - 2);
17        }
18    }
19
20    // Function to compute the power of a number 'a' raised to 'k' modulo MOD
21    public static long quickModularInverse(long a, int k) {
22        long result = 1;
23        while (k != 0) {
24            if ((k & 1) == 1) {
25                result = result * a % MOD;
26            }
27            k >>= 1;
28            a = a * a % MOD;
29        }
30        return result;
31    }
32
33    // Function to calculate the number of operations required to make the string sorted
34    public int makeStringSorted(String s) {
35        int[] charCounts = new int[26]; // Array to store the frequency of each character
36        int length = s.length(); // Get the length of the string
37      
38        // Populate the character frequency array based on the input string
39        for (int i = 0; i < length; ++i) {
40            charCounts[s.charAt(i) - 'a']++;
41        }
42      
43        long operations = 0; // Initialize the counter for operations required
44        for (int i = 0; i < length; ++i) {
45            int smallerChars = 0; // Counter for characters smaller than the current one
46          
47            // Count the characters that are lower than the current character being processed
48            for (int j = s.charAt(i) - 'a' - 1; j >= 0; --j) {
49                smallerChars += charCounts[j];
50            }
51          
52            // Calculate the contribution to the result by the current position
53            long temp = smallerChars * factorial[length - i - 1] % MOD;
54            for (int count : charCounts) {
55                temp = temp * inverseFactorial[count] % MOD;
56            }
57          
58            // Decrease the count of the current character as it is already considered
59            charCounts[s.charAt(i) - 'a']--;
60          
61            // Update the total operations, taking care of negative values with MOD
62            operations = (operations + temp + MOD) % MOD;
63        }
64      
65        // Return the calculated operations number as an integer
66        return (int) operations;
67    }
68}
69

C++ Solution

1#include <string>
2using namespace std;
3
4const int N = 3010;
5const int MOD = 1e9 + 7; // Define the modulus for arithmetic operations
6long factorial[N]; // Precomputed factorials
7long modularInverseFactorial[N]; // Precomputed modular inverses of the factorials
8
9// Fast exponentiation with modulus to compute a^k % MOD efficiently
10long quickModularExponent(long a, int k) {
11    long result = 1;
12    while (k != 0) {
13        if ((k & 1) == 1) {
14            result = result * a % MOD;
15        }
16        k >>= 1;
17        a = a * a % MOD;
18    }
19    return result;
20}
21
22// An immediately invoked lambda function to initialize factorials and their modular inverses
23int init = []() {
24    factorial[0] = modularInverseFactorial[0] = 1;
25    for (int i = 1; i < N; ++i) {
26        factorial[i] = factorial[i - 1] * i % MOD;
27        modularInverseFactorial[i] = quickModularExponent(factorial[i], MOD - 2);
28    }
29    return 0;
30}();
31
32class Solution {
33public:
34    int makeStringSorted(string s) {
35        int frequency[26] = {}; // Frequency array for characters 'a' to 'z'
36        // Count the frequency of each character in the input string
37        for (char& c : s) {
38            ++frequency[c - 'a'];
39        }
40        int n = s.size(); // Size of the input string
41        long answer = 0;
42        // Iterate over each character of the input string
43        for (int i = 0; i < n; ++i) {
44            int smallerCharsCount = 0;
45            // Count characters smaller than the current one
46            for (int j = s[i] - 'a' - 1; j >= 0; --j) {
47                smallerCharsCount += frequency[j];
48            }
49            // Compute the number of permutations leading with smaller characters
50            long term = smallerCharsCount * factorial[n - i - 1] % MOD;
51            // Multiply by the modular inverses of the factorials of the frequencies
52            for (int& value : frequency) {
53                term = term * modularInverseFactorial[value] % MOD;
54            }
55            // Add the permutations count to the answer and adjust for modulus
56            answer = (answer + term) % MOD;
57            // Decrease the frequency of the character that's been fixed in the permutation
58            --frequency[s[i] - 'a'];
59        }
60        return answer;
61    }
62};
63

Typescript Solution

1const N = 3010;
2const MOD = 1e9 + 7; // Define the modulus for arithmetic operations
3
4// Precomputed factorials array
5let factorials: number[] = new Array(N); 
6// Precomputed modular inverses of the factorials array
7let modularInverseFactorials: number[] = new Array(N); 
8
9/**
10 * Fast exponentiation with modulus to compute a^k % MOD efficiently
11 *
12 * @param base - The base of the exponentiation
13 * @param exponent - The exponent
14 * @returns The base raised to the exponent under modulo MOD
15 */
16function quickModularExponent(base: number, exponent: number): number {
17    let result = 1;
18    while (exponent !== 0) {
19        if ((exponent & 1) === 1) {
20            result = (result * base) % MOD;
21        }
22        exponent >>= 1;
23        base = (base * base) % MOD;
24    }
25    return result;
26}
27
28// Immediately invoked function expression to initialize factorials and their modular inverses
29(function initializeFactorials() {
30    factorials[0] = modularInverseFactorials[0] = 1;
31    for (let i = 1; i < N; ++i) {
32        factorials[i] = (factorials[i - 1] * i) % MOD;
33        modularInverseFactorials[i] = quickModularExponent(factorials[i], MOD - 2);
34    }
35})();
36
37/**
38 * Calculate the number of moves required to make a string sorted in lexicographical order.
39 *
40 * @param s - The input string
41 * @returns The number of moves required
42 */
43function makeStringSorted(s: string): number {
44    let frequency: number[] = new Array(26).fill(0); // Frequency array for characters 'a' to 'z'
45  
46    // Count the frequency of each character in the input string
47    for (const c of s) {
48        ++frequency[c.charCodeAt(0) - 'a'.charCodeAt(0)];
49    }
50
51    let n = s.length; // Size of the input string
52    let answer = 0;
53
54    // Iterate over each character of the input string
55    for (let i = 0; i < n; ++i) {
56        let smallerCharsCount = 0;
57        // Count characters smaller than the current one
58        for (let j = s.charCodeAt(i) - 'a'.charCodeAt(0) - 1; j >= 0; --j) {
59            smallerCharsCount += frequency[j];
60        }
61
62        // Compute the number of permutations leading with smaller characters
63        let term = (smallerCharsCount * factorials[n - i - 1]) % MOD;
64
65        // Multiply by the modular inverses of the factorials of the frequencies
66        for (const value of frequency) {
67            term = (term * modularInverseFactorials[value]) % MOD;
68        }
69
70        // Add the permutations count to the answer and adjust for modulus
71        answer = (answer + term) % MOD;
72
73        // Decrease the frequency of the character that's been fixed in the permutation
74        --frequency[s.charCodeAt(i) - 'a'.charCodeAt(0)];
75    }
76
77    return answer;
78}
79

Time and Space Complexity

The given Python code is designed to compute the number of permutations that are lexicographically smaller than the input string s, using modular arithmetic with a modulus of mod = 10**9 + 7.

Time Complexity

The time complexity can be analyzed as follows:

  1. The initialization of lists f and g has a complexity of O(n), where n is the length of f and g.

  2. The loop to compute f and g also runs in O(n), as it iterates once for each of the n elements, and each operation within the loop (multiplication, modulo, and power operation) is O(1) in time complexity (since the modular exponentiation is computed in logarithmic time relative to the exponent).

  3. Inside the makeStringSorted method, there is a loop that goes over each character of the string s. The length of s could be n at most, so this loop could iterate n times.

  4. Inside this loop, there is a sum operation which in the worst case can iterate over 26 characters (all lowercase English letters), so this part is O(1) as the number of lowercase English letters is constant.

  5. Computation of t inside the loop is O(1) as it involves a single multiplication and module operation.

  6. The most expensive operation inside the loop is the subsequent loop which computes the multiplication of t with g[v] for each value v in cnt values. Since there can be at most 26 unique characters, this loop runs in O(1) time complexity.

  7. Updating the cnt dictionary is O(1) since dictionaries in Python have average-case constant time insertions, deletions, and lookups.

Considering these steps, each iteration of the loop is O(1). Therefore, the overall time complexity for the makeStringSorted function is O(n).

Space Complexity

The space complexity can be analyzed as follows:

  1. The f and g arrays each require O(n) space to store the factorial and the modular multiplicative inverses, respectively.

  2. The Counter instance cnt will store at most 26 unique characters with their counts, which is O(1).

  3. Temporary variables used within the for loops such as i, c, m, t take O(1) space.

Therefore, the dominant term in the space complexity is the storage for f and g, which results in an overall space complexity of O(n).

To summarize, the time complexity of the code is O(n), and the space complexity is O(n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫