Skip to content

3863. Minimum Operations to Sort a String

Description

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.

Solutions

Solution 1: Case Analysis

We first check whether the string is already sorted in ascending order; if so, return 0.

Otherwise, if the string has length 2, since we cannot choose the entire string to sort, it is impossible to sort the string, so we return -1.

Next, we find the minimum character \(mn\) and the maximum character \(mx\) in the string. If the first character of the string equals \(mn\), or the last character equals \(mx\), then one operation on the remaining substring is sufficient to sort the entire string, so we return 1.

Otherwise, if some character in the middle of the string equals \(mn\) or \(mx\), we need one operation to move that character to the beginning or the end of the string, and then one more operation to sort the rest, so we return 2.

Finally, if none of the above cases apply, we need one operation on the substring containing both \(mn\) and \(mx\), followed by one more operation on the remaining substring, so we return 3.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minOperations(self, s: str) -> int:
        if all(a <= b for a, b in pairwise(s)):
            return 0
        if len(s) == 2:
            return -1
        mn, mx = min(s), max(s)
        if s[0] == mn or s[-1] == mx:
            return 1
        if any(c in [mn, mx] for c in s[1:-1]):
            return 2
        return 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int minOperations(String s) {
        boolean isSorted = true;
        char[] cs = s.toCharArray();
        int n = cs.length;
        char mn = cs[0], mx = cs[0];
        for (int i = 1; i < n; ++i) {
            mn = (char) Math.min(mn, cs[i]);
            mx = (char) Math.max(mx, cs[i]);
            if (cs[i] < cs[i - 1]) {
                isSorted = false;
            }
        }
        if (isSorted) {
            return 0;
        }
        if (n == 2) {
            return -1;
        }
        if (cs[0] == mn || cs[n - 1] == mx) {
            return 1;
        }
        for (int i = 1; i < n - 1; ++i) {
            if (cs[i] == mn || cs[i] == mx) {
                return 2;
            }
        }
        return 3;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int minOperations(string s) {
        int n = s.size();
        bool sorted = true;

        for (int i = 1; i < n; ++i) {
            if (s[i] < s[i - 1]) {
                sorted = false;
                break;
            }
        }

        if (sorted) {
            return 0;
        }

        if (n == 2) {
            return -1;
        }

        char mn = *min_element(s.begin(), s.end());
        char mx = *max_element(s.begin(), s.end());

        if (s[0] == mn || s[n - 1] == mx) {
            return 1;
        }

        for (int i = 1; i < n - 1; ++i) {
            if (s[i] == mn || s[i] == mx) {
                return 2;
            }
        }

        return 3;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func minOperations(s string) int {
    n := len(s)

    sorted := true
    for i := 1; i < n; i++ {
        if s[i] < s[i-1] {
            sorted = false
            break
        }
    }

    if sorted {
        return 0
    }

    if n == 2 {
        return -1
    }

    mn, mx := s[0], s[0]
    for i := 1; i < n; i++ {
        if s[i] < mn {
            mn = s[i]
        }
        if s[i] > mx {
            mx = s[i]
        }
    }

    if s[0] == mn || s[n-1] == mx {
        return 1
    }

    for i := 1; i < n-1; i++ {
        if s[i] == mn || s[i] == mx {
            return 2
        }
    }

    return 3
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function minOperations(s: string): number {
    const n = s.length;

    let sorted = true;
    for (let i = 1; i < n; i++) {
        if (s[i] < s[i - 1]) {
            sorted = false;
            break;
        }
    }

    if (sorted) {
        return 0;
    }

    if (n === 2) {
        return -1;
    }

    let mn = s[0];
    let mx = s[0];

    for (const c of s) {
        if (c < mn) {
            mn = c;
        }
        if (c > mx) {
            mx = c;
        }
    }

    if (s[0] === mn || s[n - 1] === mx) {
        return 1;
    }

    for (let i = 1; i < n - 1; i++) {
        if (s[i] === mn || s[i] === mx) {
            return 2;
        }
    }

    return 3;
}

Comments