Medium

题目描述

给你一个由小写英文字母组成的字符串 s。

在一次操作中，你可以选择 s 的任何一个子串（不能是整个字符串）并将其按非递减字母顺序排序。

返回使 s 按非递减顺序排序所需的最少操作次数。如果不可能，返回 -1。

示例 1：

输入：s = "dog"
输出：1
解释：
对子串 "og" 进行排序得到 "go"。
现在，s = "dgo"，已按升序排序。因此，答案是 1。

示例 2：

输入：s = "card"
输出：2
解释：
对子串 "car" 进行排序得到 "acr"，所以 s = "acrd"。
对子串 "rd" 进行排序得到 "dr"，使得 s = "acdr"，已按升序排序。因此，答案是 2。

示例 3：

输入：s = "gf"
输出：-1
解释：
在给定约束下无法对 s 进行排序。因此，答案是 -1。

约束：

  • 1 <= s.length <= 10^5
  • s 只包含小写英文字母。

提示：

  • 如果 s 已经排序，答案是 0。
  • 设 mn 为最小字符，mx 为最大字符；如果 mn 出现在开头（不是整个字符串）或 mx 出现在末尾（不是整个字符串），答案是 1。
  • 如果 s 不能转换为排序字符串，返回 -1。
  • 如果没有 mn 存在于任何真前缀中，也没有 mx 存在于任何真后缀中，答案是 3；否则答案是 2。

解题思路

这道题的关键在于理解操作的限制：我们不能对整个字符串进行排序，只能对真子串进行排序。

核心思路：

  1. 已排序：如果字符串已经是非递减的，返回 0。

  2. 一次操作：如果可以通过一次操作完成，需要满足以下条件之一：

    • 最小字符出现在字符串开头的某个位置（但不能是整个字符串）
    • 最大字符出现在字符串末尾的某个位置（但不能是整个字符串）

  3. 不可能完成：对于长度为 2 的字符串，如果第一个字符大于第二个字符，且不满足一次操作的条件，则不可能完成。

  4. 两次操作：如果不是上述情况，检查是否可以通过两次操作完成：

    • 最小字符出现在某个真前缀中，或
    • 最大字符出现在某个真后缀中

  5. 三次操作：如果以上都不满足，则需要 3 次操作。

算法步骤：

  1. 找到字符串中的最小字符和最大字符
  2. 检查字符串是否已经排序
  3. 按照上述逻辑依次判断需要的操作次数

这种方法基于对问题的数学分析，通过分类讨论覆盖所有可能的情况。

代码实现

class Solution {
public:
    int minOperations(string s) {
        int n = s.length();
        if (n == 1) return 0;
        
        // Check if already sorted
        bool sorted = true;
        for (int i = 1; i < n; i++) {
            if (s[i] < s[i-1]) {
                sorted = false;
                break;
            }
        }
        if (sorted) return 0;
        
        // Find min and max characters
        char minChar = *min_element(s.begin(), s.end());
        char maxChar = *max_element(s.begin(), s.end());
        
        // Check for 1 operation
        // Min char at beginning (but not whole string)
        if (s[0] == minChar && n > 1) return 1;
        // Max char at end (but not whole string)
        if (s[n-1] == maxChar && n > 1) return 1;
        
        // Special case for length 2
        if (n == 2) return -1;
        
        // Check for 2 operations
        // Min char in proper prefix
        for (int i = 0; i < n-1; i++) {
            if (s[i] == minChar) return 2;
        }
        // Max char in proper suffix
        for (int i = 1; i < n; i++) {
            if (s[i] == maxChar) return 2;
        }
        
        // Otherwise 3 operations
        return 3;
    }
};

class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)
        if n == 1:
            return 0
        
        # Check if already sorted
        if s == ''.join(sorted(s)):
            return 0
        
        # Find min and max characters
        min_char = min(s)
        max_char = max(s)
        
        # Check for 1 operation
        # Min char at beginning (but not whole string)
        if s[0] == min_char and n > 1:
            return 1
        # Max char at end (but not whole string)
        if s[n-1] == max_char and n > 1:
            return 1
        
        # Special case for length 2
        if n == 2:
            return -1
        
        # Check for 2 operations
        # Min char in proper prefix
        for i in range(n-1):
            if s[i] == min_char:
                return 2
        # Max char in proper suffix
        for i in range(1, n):
            if s[i] == max_char:
                return 2
        
        # Otherwise 3 operations
        return 3

public class Solution {
    public int MinOperations(string s) {
        int n = s.Length;
        if (n == 1) return 0;
        
        // Check if already sorted
        bool sorted = true;
        for (int i = 1; i < n; i++) {
            if (s[i] < s[i-1]) {
                sorted = false;
                break;
            }
        }
        if (sorted) return 0;
        
        // Find min and max characters
        char minChar = s.Min();
        char maxChar = s.Max();
        
        // Check for 1 operation
        // Min char at beginning (but not whole string)
        if (s[0] == minChar && n > 1) return 1;
        // Max char at end (but not whole string)
        if (s[n-1] == maxChar && n > 1) return 1;
        
        // Special case for length 2
        if (n == 2) return -1;
        
        // Check for 2 operations
        // Min char in proper prefix
        for (int i = 0; i < n-1; i++) {
            if (s[i] == minChar) return 2;
        }
        // Max char in proper suffix
        for (int i = 1; i < n; i++) {
            if (s[i] == maxChar) return 2;
        }
        
        // Otherwise 3 operations
        return 3;
    }
}

var minOperations = function(s) {
    const n = s.length;
    if (n === 1) return 0;
    
    // Check if it's possible - count inversions
    let inversions = 0;
    for (let i = 0; i < n - 1; i++) {
        if (s[i] > s[i + 1]) {
            inversions++;
        }
    }
    
    if (inversions === 0) return 0;
    
    // Special case: if string is reverse sorted, it's impossible
    if (s === s.split('').sort().reverse().join('')) {
        return -1;
    }
    
    let operations = 0;
    let arr = s.split('');
    
    while (!isSorted(arr)) {
        let found = false;
        
        // Try to find a substring that when sorted improves the overall order
        for (let i = 0; i < n - 1; i++) {
            for (let j = i + 1; j < n; j++) {
                // Don't sort the entire string
                if (i === 0 && j === n - 1) continue;
                
                let substring = arr.slice(i, j + 1);
                let sorted = [...substring].sort();
                
                // Check if sorting this substring moves us closer to sorted
                if (!arraysEqual(substring, sorted)) {
                    let newArr = [...arr];
                    for (let k = 0; k < sorted.length; k++) {
                        newArr[i + k] = sorted[k];
                    }
                    
                    if (countInversions(newArr) < countInversions(arr)) {
                        arr = newArr;
                        operations++;
                        found = true;
                        break;
                    }
                }
            }
            if (found) break;
        }
        
        if (!found) return -1;
        if (operations > n) return -1; // Prevent infinite loop
    }
    
    return operations;
};

function isSorted(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) return false;
    }
    return true;
}

function arraysEqual(a, b) {
    return a.length === b.length && a.every((val, i) => val === b[i]);
}

function countInversions(arr) {
    let count = 0;
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) count++;
    }
    return count;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串找到最小最大字符，检查排序状态，最坏情况下遍历常数次
空间复杂度O(1)只使用常数级别的额外空间存储最小最大字符等变量