Scale Engineer

Minimum Number of Operations to Make String Sorted

Hard
#1673Time: O(K * N), where `N` is the length of the string and `K` is the total number of operations. `K` can be very large, making this approach impractical.Space: O(N) to store the character array.1 company
Patterns
MathCombinatorics
Data structures
String
Companies
Samsung

Prompt

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 109 + 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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We start with the given string and repeatedly apply the "previous permutation" operation until the string becomes sorted. We count the number of operations performed.

Algorithm

  • Initialize count = 0.
  • Convert the input string s to a character array chars.
  • Start an infinite loop:
    • Find the largest index i such that 1 <= i < n and chars[i] < chars[i-1].
    • If no such i exists, the string is sorted. Break the loop.
    • Find the largest index j such that i <= j < n and chars[j] < chars[i-1].
    • Swap chars[i-1] and chars[j].
    • Reverse the subarray of chars from index i to the end.
    • Increment count (modulo 10^9 + 7).
  • Return count.

Walkthrough

The algorithm involves a loop that continues as long as the string is not sorted. Inside the loop, we perform one operation as defined:

  1. Find the largest index i where s[i] < s[i-1]. This identifies the pivot point for generating the previous permutation.
  2. Find the largest index j in the suffix s[i:] such that s[j] < s[i-1]. This finds the character to swap with the pivot.
  3. Swap the characters at i-1 and j.
  4. Reverse the suffix of the string starting from index i. We maintain a counter which is incremented in each iteration of the loop. The simulation stops when the string is lexicographically sorted, and we return the final count. Since the string is modified in place, we convert it to a character array for easier manipulation.
class Solution {    public int makeStringSorted(String s) {        long count = 0;        long MOD = 1_000_000_007;        char[] chars = s.toCharArray();        int n = s.length();         while (true) {            int i = n - 1;            while (i > 0 && chars[i] >= chars[i - 1]) {                i--;            }             if (i == 0) {                // String is sorted                break;            }             int pivot = i - 1;            int j = n - 1;            while (j >= i && chars[j] >= chars[pivot]) {                j--;            }                        swap(chars, pivot, j);            reverse(chars, i, n - 1);                        count = (count + 1) % MOD;        }        return (int) count;    }     private void swap(char[] chars, int i, int j) {        char temp = chars[i];        chars[i] = chars[j];        chars[j] = temp;    }     private void reverse(char[] chars, int start, int end) {        while (start < end) {            swap(chars, start, end);            start++;            end--;        }    }}

Complexity

Time

O(K * N), where `N` is the length of the string and `K` is the total number of operations. `K` can be very large, making this approach impractical.

Space

O(N) to store the character array.

Trade-offs

Pros

  • Simple to understand and implement as it directly follows the problem description.

Cons

  • Extremely inefficient. The number of operations can be astronomically large (related to n!), causing the simulation to be too slow for the given constraints (n up to 3000). This will result in a Time Limit Exceeded (TLE) error.

Solutions

class Solution { private static final int N = 3010 ; private static final int MOD = ( int ) 1 e9 + 7 ; private static final long [] f = new long [ N ]; private static final long [] g = new long [ N ]; static { f [ 0 ] = 1 ; g [ 0 ] = 1 ; for ( int i = 1 ; i < N ; ++ i ) { f [ i ] = f [ i - 1 ] * i % MOD ; g [ i ] = qmi ( f [ i ], MOD - 2 ); } } public static long qmi ( long a , int k ) { long res = 1 ; while ( k != 0 ) { if (( k & 1 ) == 1 ) { res = res * a % MOD ; } k >>= 1 ; a = a * a % MOD ; } return res ; } public int makeStringSorted ( String s ) { int [] cnt = new int [ 26 ]; int n = s . length (); for ( int i = 0 ; i < n ; ++ i ) { ++ cnt [ s . charAt ( i ) - 'a' ]; } long ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int m = 0 ; for ( int j = s . charAt ( i ) - 'a' - 1 ; j >= 0 ; -- j ) { m += cnt [ j ]; } long t = m * f [ n - i - 1 ] % MOD ; for ( int v : cnt ) { t = t * g [ v ] % MOD ; } -- cnt [ s . charAt ( i ) - 'a' ]; ans = ( ans + t + MOD ) % MOD ; } return ( int ) ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem