Description
Minimum Operations to Sort a String
MediumYou 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", sos = "acrd". - Sort substring
"rd"to"dr", makings = "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
sunder the given constraints. Thus, the answer is -1.
Constraints:
1 <= s.length <= 105sconsists of only lowercase English letters.
Solutions
Very interesting and fun exercise.
Language: javascript()DONE
CPU Performance96.69%
x
Memory Performance74.10%
x
/**
* @param {string} s
* @return {number}
*/
var minOperations = function(s) {
let min = 123;
let minc = 0;
let max = 97;
let maxc = 0;
let sorted = true;
for (let i = 0; i < s.length; i++) {
const code = s.charCodeAt(i);
if (code < min) {
min = code;
minc = 1;
} else if (code === min) {
minc++;
}
if (code > max) {
max = code;
maxc = 1;
} else if (code === max) {
maxc++;
}
if (i > 0 && code < s.charCodeAt(i - 1)) {
sorted = false;
}
}
const codeFirst = s.charCodeAt(0);
const codeLast = s.charCodeAt(s.length - 1);
if (sorted) return 0;
if (s.length <= 2) return -1;
if (codeFirst === min || codeLast === max) return 1;
if (codeFirst === max && maxc === 1 && codeLast === min && minc === 1) return 3;
return 2;
};