Minimum Number of Operations to Make String Sorted
HardPrompt
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
isuch that1 <= i < s.lengthands[i] < s[i - 1]. - Find the largest index
jsuch thati <= j < s.lengthands[k] < s[i - 1]for all the possible values ofkin the range[i, j]inclusive. - Swap the two characters at indices
i - 1 andj. - 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 <= 3000s 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:
- Find the largest index
iwheres[i] < s[i-1]. This identifies the pivot point for generating the previous permutation. - Find the largest index
jin the suffixs[i:]such thats[j] < s[i-1]. This finds the character to swap with the pivot. - Swap the characters at
i-1andj. - 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 (nup to 3000). This will result in a Time Limit Exceeded (TLE) error.
Solutions
Solution
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.