Minimum Number of Operations to Make String Sorted

Minimum Number of Operations to Make String Sorted - Problem

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.

Input & Output

Example 1 — Small String

$ Input: s = "cba"

› Output: 5

💡 Note: The operations transform: "cba" → "cab" → "acb" → "abc". Total operations needed: 5

Example 2 — Already Sorted

$ Input: s = "aabbc"

› Output: 0

💡 Note: String is already sorted, so no operations are needed

Example 3 — Reverse Order

$ Input: s = "dcba"

› Output: 11

💡 Note: Worst case: completely reverse sorted string requires 11 operations to sort

Constraints

1 ≤ s.length ≤ 3000
s consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Unsorted string like "cba"

Operations

Apply the 4-step operation repeatedly

Output

Count of operations needed (5 for "cba")

Key Takeaway

🎯 Key Insight: The operations are reverse next-permutation - use factorial number system to calculate directly instead of simulating

Asked in

G Google 15 a Amazon 8 M Microsoft 5

This problem asks us to count operations to sort a string using a specific reverse next-permutation algorithm. The key insight is that instead of simulating the operations, we can use factorial number system and combinatorics to calculate the result mathematically. The optimal approach uses character frequencies and factorials to count permutations in O(n²) time with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Simulation Approach	O(n! × n)	O(1)	Simulate the exact operations described until string becomes sorted
Factorial Number System (Combinatorics)	O(n²)	O(n)	Convert the problem to factorial number system and calculate operations mathematically

Simulation Approach — Algorithm Steps

Repeatedly find largest index i where s[i] < s[i-1]
Find largest j where all characters in [i,j] are < s[i-1]
Swap s[i-1] and s[j], then reverse suffix from i
Count operations until string is sorted

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Pivot

Find largest i where s[i] < s[i-1]

Find Swap Target

Find largest j where all chars [i,j] < s[i-1]

Swap & Reverse

Swap characters and reverse suffix

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void reverse(char* s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
}

int solution(char* s) {
    const int MOD = 1000000007;
    int len = strlen(s);
    int operations = 0;
    
    while (1) {
        // Find largest i where s[i] < s[i-1]
        int i = -1;
        for (int k = 1; k < len; k++) {
            if (s[k] < s[k-1]) {
                i = k;
            }
        }
        
        if (i == -1) break; // String is sorted
        
        // Find largest j where all chars in [i,j] are < s[i-1]
        int j = i;
        for (int k = i; k < len; k++) {
            if (s[k] < s[i-1]) {
                j = k;
            } else {
                break;
            }
        }
        
        // Swap s[i-1] and s[j]
        char temp = s[i-1];
        s[i-1] = s[j];
        s[j] = temp;
        
        // Reverse suffix starting at i
        reverse(s, i, len - 1);
        
        operations = (operations + 1) % MOD;
    }
    
    return operations;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Factorial permutations possible, each operation takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(1)

Only modifying string in-place with constant extra variables

✓ Linear Space

12.0K Views

Medium Frequency

~45 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler