We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Make String Sorted

Difficulty: Hard

Problem Description

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

  1. Find the largest index i such that 1 <= i < s.length and s[i] < s[i - 1].
  2. 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.
  3. Swap the two characters at indices i - 1 and j.
  4. 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^9 + 7.

Key Insights

  • The operations are primarily focused on identifying positions in the string that break the sorted order.
  • The algorithm involves repeatedly finding indices i and j, which depend on the relative ordering of characters in the string.
  • The operations can be seen as a series of swaps and reversals that progressively sort the string.
  • The complexity of the operations indicates that a brute-force approach may not be efficient, especially for longer strings.

Space and Time Complexity

Time Complexity: O(n^2) where n is the length of the string, due to the nested operations for identifying indices and performing swaps. Space Complexity: O(1) as we are using a constant amount of space for indices and counters.

Solution

The approach to solve this problem involves simulating the operations described in the problem statement. The main steps of the solution include:

  1. Identify the index i: Traverse the string from right to left to find the largest index i where s[i] < s[i - 1].
  2. Identify the index j: Once i is found, traverse from i to the end of the string to find the largest index j where s[j] < s[i - 1].
  3. Perform the swap: Swap the characters at indices i - 1 and j.
  4. Reverse the suffix: Reverse the substring from index i to the end of the string.
  5. Count the operations: Repeat the process until the string is sorted, counting each operation.

This systematic approach ensures we effectively transition the string towards a sorted order while counting the number of operations.

Code Solutions

def minOperations(s: str) -> int:
    MOD = 10**9 + 7
    operations = 0
    s = list(s)  # Convert string to list for mutability

    while True:
        i = -1
        # Step 1: Find the largest index i
        for k in range(len(s) - 1, 0, -1):
            if s[k] < s[k - 1]:
                i = k
                break
        
        if i == -1:  # If no such i found, the string is sorted
            break

        j = -1
        # Step 2: Find the largest index j
        for k in range(i, len(s)):
            if s[k] < s[i - 1]:
                j = k
        
        # Step 3: Swap
        s[i - 1], s[j] = s[j], s[i - 1]
        
        # Step 4: Reverse the suffix
        s[i:] = s[i:][::-1]
        
        operations = (operations + 1) % MOD

    return operations
← Back to All Questions