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:
- Identify the largest index
i
satisfying1 <= i < s.length
such that the character ats[i]
is less than the character ats[i - 1]
. - Find the largest index
j
greater than or equal toi
such that every character at positionk
within the range[i, j]
is less than the character ats[i - 1]
. - Swap the characters at positions
i - 1
andj
. - 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:
-
Calculate factorial
f
and modulo multiplicative inverseg
in advance for efficient computation during iteration. -
Use a counter to keep track of the number of occurrences of each character in the string.
-
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 countv
. -
Update the total count
ans
of operations needed, by addingt
modulo10^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.
-
-
The computed
ans
is returned which gives us the required number of operations modulo10^9 + 7
. -
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.
Learn more about Math and Combinatorics patterns.
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:
-
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 arrayg
.
This is a preprocessing step to speed up the calculations needed for each operation count later on.
- Factorials of all possible index positions are precalculated and stored in an array
-
Using
Counter
to keep track of character frequencies:- A
Counter
from thecollections
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.
- A
-
Main algorithmic loop:
-
We loop over each character
c
in the strings
with its indexi
. 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 thanc
that are currently placed to the right of their target position. -
Compute the partial operations count
t
by multiplying the factorialf[n - i - 1]
(representing the permutations of remaining characters) by the numberm
. -
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.
-
-
Combination of counts and modular arithmetic:
- Each partial count
t
is added to the total answerans
, with modulo10^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.
- Each partial count
-
Final result:
- Once the loop is done, the resulting
ans
variable holds the total count of operations needed to sort the string, modulo10^9 + 7
.
- Once the loop is done, the resulting
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example with the string s = "bca"
and walk through the solution approach.
-
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 modulomod
)g = [1, 1, 500000004, 166666668]
(inverses modulomod
)
-
Using
Counter
to keep track of character frequencies:By counting the occurrences of each character, we get:
- Counter = {'b': 1, 'c': 1, 'a': 1}
-
Main algorithmic loop:
Now, we iterate over the string:
-
For character
b
at index 0:m
is the count of characters less thanb
to its right, which is 1 ('a').- Calculate permutation count
t
asm * f[n - i - 1]
, which gives1 * f[2]
- Correct for any duplicates, which isn't necessary here as all counts are 1.
t
is now1 * 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 thanc
to its right, which is 1 ('a').- Calculate permutation count
t
asm * f[n - i - 1]
, which gives1 * f[1]
- Correct for any duplicates, which again isn't needed.
t
is1 * 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
.
-
-
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".
- By summing the partial counts (while taking
-
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.
Solution Implementation
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
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
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
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:
-
The initialization of lists
f
andg
has a complexity ofO(n)
, wheren
is the length off
andg
. -
The loop to compute
f
andg
also runs inO(n)
, as it iterates once for each of then
elements, and each operation within the loop (multiplication, modulo, and power operation) isO(1)
in time complexity (since the modular exponentiation is computed in logarithmic time relative to the exponent). -
Inside the
makeStringSorted
method, there is a loop that goes over each character of the strings
. The length ofs
could ben
at most, so this loop could iteraten
times. -
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 isO(1)
as the number of lowercase English letters is constant. -
Computation of
t
inside the loop isO(1)
as it involves a single multiplication and module operation. -
The most expensive operation inside the loop is the subsequent loop which computes the multiplication of
t
withg[v]
for each valuev
incnt
values. Since there can be at most26
unique characters, this loop runs inO(1)
time complexity. -
Updating the
cnt
dictionary isO(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:
-
The
f
andg
arrays each requireO(n)
space to store the factorial and the modular multiplicative inverses, respectively. -
The
Counter
instancecnt
will store at most26
unique characters with their counts, which isO(1)
. -
Temporary variables used within the for loops such as
i, c, m, t
takeO(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)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.