Minimum Number of Operations to Make String Sorted

Hard

Samsung

1 view

Topics:

ArraysGreedy Algorithms

You are given a string s (0-indexed). You are asked to perform the following operation on s until you get a sorted string:

Find the largest index i such that 1 <= i < s.length and s[i] < s[i - 1].
Find the largest index j such that i <= j < s.length and s[k] < s[i - 1] for all the possible values of k in the range [i, j] inclusive.
Swap the two characters at indices i - 1 and j.
Reverse the suffix starting at index i.

Return the number of operations needed to make the string sorted. Since the answer can be too large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "cba"
Output: 5
Explanation: 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
Explanation: 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.

Minimum Number of Operations to Make String Sorted

Hard

Samsung

1 view

Topics:

ArraysGreedy Algorithms

You are given a string s (0-indexed). You are asked to perform the following operation on s until you get a sorted string:

Find the largest index i such that 1 <= i < s.length and s[i] < s[i - 1].
Find the largest index j such that i <= j < s.length and s[k] < s[i - 1] for all the possible values of k in the range [i, j] inclusive.
Swap the two characters at indices i - 1 and j.
Reverse the suffix starting at index i.

Return the number of operations needed to make the string sorted. Since the answer can be too large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "cba"
Output: 5
Explanation: 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
Explanation: 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

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`? Are there any memory constraints I should be aware of?
Can the input string `s` be empty or null? If so, what should the function return in those cases?
If the string is already sorted, should the function return 0?
The problem description mentions finding the *smallest* character to the right for the swap. If multiple characters meet that criteria, which one should be chosen?
The problem statement requires calculating the result modulo 10^9 + 7. Can you confirm this is only for the final result, and not for intermediate calculations within the algorithm?

Brute Force Solution

Approach

The brute force method for sorting a string involves exploring every single way to rearrange the characters. We consider each possible swap or reordering and calculate how many operations it takes to achieve a sorted state. Ultimately, we select the arrangement that requires the fewest operations.

Here's how the algorithm would work step-by-step:

Start by listing out all the possible arrangements (permutations) of the string's characters.
For each arrangement, compare it to the truly sorted arrangement of the characters.
Count how many 'moves' or operations it would take to transform that arrangement into the sorted one.
Keep track of the arrangement that needs the fewest operations to become sorted.
After checking every possible arrangement, the arrangement with the smallest number of operations is your answer.

Code Implementation

import itertools

def minimum_number_of_operations_to_make_string_sorted_brute_force(input_string):
    all_permutations = list(itertools.permutations(input_string))
    
    sorted_string = ''.join(sorted(input_string))
    minimum_operations = float('inf')

    for permutation_tuple in all_permutations:
        permutation_string = ''.join(permutation_tuple)
        
        # Need to compare against the sorted string
        operations = 0
        for index in range(len(input_string)):
            if permutation_string[index] != sorted_string[index]:
                operations += 1
                
        # Keep track of minimum operation
        minimum_operations = min(minimum_operations, operations)

    return minimum_operations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n! * n) – The provided approach first generates all possible permutations of the string, which has a time complexity of O(n!), where n is the length of the string. Then, for each permutation, it compares it to the sorted version of the string to count the number of operations required. Comparing each permutation, which has length n, takes O(n) time. Since we perform this comparison for each of the n! permutations, the overall time complexity is O(n! * n).

Space Complexity

O(N!) – The brute force approach necessitates generating all permutations of the input string, which results in N! possible arrangements, where N is the length of the string. To store these permutations, the algorithm implicitly creates a data structure, such as a list or a set, which could grow up to the size of N!. Comparing each permutation to the sorted string doesn't introduce significant additional space. Therefore, the space complexity is dominated by the storage of permutations, leading to O(N!).

Optimal Solution

Approach

To find the minimum operations to sort a string, we think about how many ways we could have arranged the string to begin with if it was already sorted *before* the operations. Then, for each position in the string, we figure out how many smaller characters are to the right, and how many arrangements we skip because of those smaller characters. This gives us the number of operations needed.

Here's how the algorithm would work step-by-step:

Calculate the total number of possible arrangements of the string as if it were sorted originally, keeping in mind that repeated characters reduce the number of distinct arrangements.
Go through the string from left to right, one character at a time.
For each character, count how many characters to its right are smaller than it.
The number of smaller characters tells you how many sorted arrangements would come before the current one, if we only considered the characters to the right of the current position.
Adjust the total number of arrangements by subtracting the arrangements that were skipped because of the smaller characters found at each position.
Make sure to account for repeated characters at each step to avoid overcounting skipped arrangements.
After going through each character, the final number represents the minimum operations to sort the original string.

Code Implementation

def minimum_operations_to_sort_string(word):
    string_length = len(word)
    MOD = 10**9 + 7
    fact = [1] * (string_length + 1)
    for i in range(1, string_length + 1):
        fact[i] = (fact[i - 1] * i) % MOD

    def power(base, exponent):
        result = 1
        base %= MOD
        while exponent > 0:
            if exponent % 2 == 1:
                result = (result * base) % MOD
            base = (base * base) % MOD
            exponent //= 2
        return result

    def inverse(number):
        return power(number, MOD - 2)

    operations = 0
    for i in range(string_length):
        counts = {}
        smaller_characters = 0
        for j in range(i + 1, string_length):
            if word[j] < word[i]:
                smaller_characters += 1
            counts[word[j]] = counts.get(word[j], 0) + 1

        if smaller_characters == 0:
            continue

        denominator = 1
        for count in counts.values():
            denominator = (denominator * fact[count]) % MOD

        # Calculate the number of arrangements skipped.
        arrangements_skipped = (fact[string_length - i - 1] * inverse(denominator)) % MOD
        arrangements_skipped = (arrangements_skipped * smaller_characters) % MOD
        operations = (operations + arrangements_skipped) % MOD

        # After counting skipped arrangements, proceed to next character

    return operations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The dominant operations are counting smaller characters to the right for each character in the string of length n and calculating arrangements at each step. Counting smaller characters involves iterating through the remaining portion of the string for each character, leading to nested loops. Therefore, for each of the n characters, we perform up to n comparisons, resulting in approximately n * n/2 operations. This can be simplified to O(n²).

Space Complexity

O(N) – The algorithm calculates factorials and inverse factorials. A common implementation precomputes these values and stores them in arrays for efficient calculation during the string traversal. These arrays, used to store factorial and inverse factorial values up to N (where N is the length of the string), require O(N) space. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty string input	Return 0 immediately as an empty string is already sorted.
String with a single character	Return 0 immediately as a single character string is already sorted.
String already sorted in lexicographical order	Return 0 as no operations are needed.
String sorted in reverse lexicographical order	This represents the maximum number of operations possible and should be handled efficiently by the algorithm.
String with all identical characters	Return 0, because swapping identical characters doesn't change the order.
Large input string that could lead to integer overflow when calculating the number of operations	Perform all arithmetic operations modulo 10^9 + 7 to prevent overflow.
String containing duplicate characters which may affect the smallest character to the right selection	The algorithm needs to correctly identify the smallest character to the right, even with duplicates, and the count array helps with the calculation.
Input string close to the maximum allowed size, potentially exceeding time limits	Optimize the counting and factorial calculations to operate within reasonable time complexity, using precomputation where possible.