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

Solutions

Solution 1: Case Analysis

Thinking

Each operation sorts a proper substring. We want the fewest operations to make \(s\) nondecreasing. \(|s| \le 10^5\) forbids simulating sorts.

One operation can sort any proper substring, so the answer depends only on whether the min and max letters can be moved to the ends in one or two steps.

Already sorted yields \(0\). A disordered length-\(2\) string has no proper substring covering both letters, hence \(-1\). Min already first or max already last needs one operation; one of them in the interior needs two; otherwise three.

The case split is exhaustive and checked in linear time.

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)\).

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

3863. Minimum Operations to Sort a String

Description

Solutions

Solution 1: Case Analysis

Comments