3863. Minimum Operations to Sort a String

/**
 * Problem: LeetCode 3863 - Minimum Operations to Sort a String
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int minOperations(String s) {
        int n = s.length();
        boolean sorted = true;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i - 1) > s.charAt(i)) {
                sorted = false;
                break;
            }
        }
        if (sorted) return 0;
        if (n == 2) return -1;
        char mn = 'z', mx = 'a';
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c < mn) mn = c;
            if (c > mx) mx = c;
        }
        if (s.charAt(0) == mn || s.charAt(n - 1) == mx) return 1;
        char minPrefix = 'z', maxSuffix = 'a';
        for (int i = 0; i < n - 1; i++) {
            minPrefix = (char) Math.min(minPrefix, s.charAt(i));
        }
        for (int i = 1; i < n; i++) {
            maxSuffix = (char) Math.max(maxSuffix, s.charAt(i));
        }
        boolean lastStrictMin = s.charAt(n - 1) < minPrefix;
        boolean firstStrictMax = s.charAt(0) > maxSuffix;
        if (lastStrictMin && firstStrictMax) return 3;
        return 2;
    }
}

"""
Problem: LeetCode 3863 - Minimum Operations to Sort a String
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)
        
        # Check if already sorted
        if all(s[i - 1] <= s[i] for i in range(1, n)):
            return 0
            
        # If n == 2 and not sorted, no proper substring can fix it
        if n == 2:
            return -1
            
        mn = min(s)
        mx = max(s)
        
        # If the minimum is already at the start or maximum at the end
        if s[0] == mn or s[-1] == mx:
            return 1
            
        min_prefix = min(s[:-1])
        max_suffix = max(s[1:])
        
        last_strict_min = s[-1] < min_prefix
        first_strict_max = s[0] > max_suffix
        
        if last_strict_min and first_strict_max:
            return 3
            
        return 2

/**
 * Problem: LeetCode 3863 - Minimum Operations to Sort a String
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <string>
#include <algorithm>

using namespace std;

/**
 * Problem: LeetCode 3863 - Minimum Operations to Sort a String
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
class Solution {
public:
    int minOperations(string s) {
        int n = s.length();
        bool sorted = true;
        for (int i = 1; i < n; i++) {
            if (s[i - 1] > s[i]) {
                sorted = false;
                break;
            }
        }
        if (sorted) return 0;
        if (n == 2) return -1;

        char mn = 'z', mx = 'a';
        for (char c : s) {
            if (c < mn) mn = c;
            if (c > mx) mx = c;
        }

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

        char minPrefix = 'z', maxSuffix = 'a';
        for (int i = 0; i < n - 1; i++) {
            minPrefix = min(minPrefix, s[i]);
        }
        for (int i = 1; i < n; i++) {
            maxSuffix = max(maxSuffix, s[i]);
        }

        bool lastStrictMin = s[n - 1] < minPrefix;
        bool firstStrictMax = s[0] > maxSuffix;

        if (lastStrictMin && firstStrictMax) return 3;
        return 2;
    }
};

/**
 * Problem: LeetCode 3863 - Minimum Operations to Sort a String
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
var minOperations = function(s) {
    const n = s.length;
    let sorted = true;
    for (let i = 1; i < n; i++) {
        if (s.charCodeAt(i - 1) > s.charCodeAt(i)) {
            sorted = false;
            break;
        }
    }
    if (sorted) return 0;
    if (n === 2) return -1;

    let mn = 'z', mx = 'a';
    for (let i = 0; i < n; i++) {
        const c = s[i];
        if (c < mn) mn = c;
        if (c > mx) mx = c;
    }

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

    let minPrefix = 'z', maxSuffix = 'a';
    for (let i = 0; i < n - 1; i++) {
        if (s[i] < minPrefix) minPrefix = s[i];
    }
    for (let i = 1; i < n; i++) {
        if (s[i] > maxSuffix) maxSuffix = s[i];
    }

    const lastStrictMin = s[n - 1] < minPrefix;
    const firstStrictMax = s[0] > maxSuffix;

    if (lastStrictMin && firstStrictMax) return 3;
    return 2;
};