Is Minimum Operations to Sort a String easy or hard?

Minimum Operations to Sort a String is generally considered a medium difficulty problem. The core logic is simple once you compare the string with its sorted version, but identifying the correct counting logic for operations requires careful reasoning.

Minimum Operations to Sort a String Python/Java solution

Python, Java, C++, Go, and TypeScript implementations typically follow the same structure: create a sorted version of the string, iterate through both strings, and count the positions or segments that require operations. Built-in sorting functions simplify implementation.

How to solve Minimum Operations to Sort a String in O(n)?

Pure O(n) solutions are only possible if the character range is limited and counting sort can replace comparison sorting. In that case you compute the sorted order using frequency counts, then scan the string once to detect mismatches and count required operations.

What is the best approach for Minimum Operations to Sort a String?

The most practical approach compares the original string with its sorted version and performs case analysis on mismatched positions. Sorting takes O(n log n) time and a single linear scan counts the operations needed to align characters with the sorted order. This method avoids expensive simulations and is easy to implement.

Is Minimum Operations to Sort a String asked at Google/Amazon/Meta?

String transformation and minimum operation problems are common interview patterns at companies like Google, Amazon, and Meta. Variants that involve sorting constraints, mismatch counting, or greedy corrections frequently appear in technical interviews.

What data structure is used in Minimum Operations to Sort a String?

The solution primarily uses strings or character arrays along with a sorted copy of the string. Some implementations also use frequency arrays or counters when optimizing sorting for limited character sets.

What is the time complexity of Minimum Operations to Sort a String?

The optimal solution typically runs in O(n log n) time due to sorting the string. After sorting, a single pass comparison with the original string determines where operations are needed, which costs O(n). Space complexity is O(n) for storing the sorted copy.

Description Hints 4 Solution Video 12:02

3863. Minimum Operations to Sort a String

Medium39.0% acceptance1 company

You are given a string s consisting of lowercase English letters.

In one operation, you can select any substring of s that is not the entire string and sort it in non-descending alphabetical order.

Return the minimum number of operations required to make s sorted in non-descending order. If it is not possible, return -1.

Example 1:

Input: s = "dog"

Output: 1

Explanation:

Sort substring "og" to "go".
Now, s = "dgo", which is sorted in ascending order. Thus, the answer is 1.

Example 2:

Input: s = "card"

Output: 2

Explanation:

Sort substring "car" to "acr", so s = "acrd".
Sort substring "rd" to "dr", making s = "acdr", which is sorted in ascending order. Thus, the answer is 2.

Example 3:

Input: s = "gf"

Output: -1

Explanation:

It is impossible to sort s under the given constraints. Thus, the answer is -1.

Constraints:

1 <= s.length <= 10⁵
s consists of only lowercase English letters.

Asked at 1 company

Amazon

Topics

String

Hints open one at a time

Hint 1

If s is already sorted, answer is 0.

Hint 2

Let mn be the minimum char and mx be the maximum char; if mn appears at the beginning (not whole string) or mx appears at the end (not whole string), answer is 1.

Hint 3

If s cannot be transformed into a sorted string, return -1.

Hint 4

If no mn exists in any proper prefix and no mx exists in any proper suffix, answer is 3; otherwise answer is 2

12:02

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minOperations(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"dog"

Input

"card"

Input

"gf"

Your code is saved on this device.Solution