minimum-operations-to-sort-a-string

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a string <code>s</code> consisting of lowercase English letters.

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

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

&nbsp;
Example 1:

<div class="example-block">
Input: s = &quot;dog&quot;

Output: 1

Explanation:​​​​​​​

<ul>
	<li>Sort substring <code>&quot;og&quot;</code> to <code>&quot;go&quot;</code>.</li>
	<li>Now, <code>s = &quot;dgo&quot;</code>, which is sorted in ascending order. Thus, the answer is 1.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: s = &quot;card&quot;

Output: 2

Explanation:

<ul>
	<li>Sort substring <code>&quot;car&quot;</code> to <code>&quot;acr&quot;</code>, so <code>s = &quot;acrd&quot;</code>.</li>
	<li>Sort substring <code>&quot;rd&quot;</code> to <code>&quot;dr&quot;</code>, making <code>s = &quot;acdr&quot;</code>, which is sorted in ascending order. Thus, the answer is 2.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: s = &quot;gf&quot;

Output: -1

Explanation:

<ul>
	<li>It is impossible to sort <code>s</code> under the given constraints. Thus, the answer is -1.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 105</code></li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

Weekly Contest 492

weekly-contest-492

minOperations

Staff

Minimum Operations to Sort a String

String

Accepted

Wrong Answer

Memory Limit Exceeded

Output Limit Exceeded

Time Limit Exceeded

Runtime Error

Internal Error

Compile Error

Timeout

Restrictions Failed

cangjie

react

vanillajs

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 <= 105
 * s consists of only lowercase English letters.