Easy

题目描述

给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一步操作中，你可以从 s 中删除一个回文子序列。

返回删除给定字符串中所有字符（字符串为空）的最小步数。

字符串的一个 子序列 是一个由原字符串生成的新字符串，生成过程中可能会删除原字符串中的一些字符（也可能不删除），但剩余字符的相对顺序应该保持不变。

如果一个字符串向前和向后读都相同，那么它是 回文字符串。

示例 1：

输入：s = "ababa"
输出：1
解释：字符串本身就是回文序列，只需要删除一次。

示例 2：

输入：s = "abb"
输出：2
解释："abb" -> "bb" -> ""
删除回文子序列 "a"，然后再删除 "bb"。

示例 3：

输入：s = "baabb"
输出：2
解释："baabb" -> "b" -> ""
删除回文子序列 "baab"，然后再删除 "b"。

提示：

  • 1 <= s.length <= 1000
  • s[i] 不是 'a' 就是 'b'

解题思路

这道题的关键在于理解题目要求和字符串的特殊性质。

核心观察：

  1. 字符串只包含 ‘a’ 和 ‘b’ 两种字符
  2. 我们可以删除任意的回文子序列（不需要连续）
  3. 所有相同字符组成的子序列都是回文的

解法分析：

由于字符串只包含两种字符，我们有以下情况：

  1. 如果字符串本身就是回文：只需要1步就能删除整个字符串
  2. 如果字符串不是回文：最多需要2步
    • 第一步：删除所有的 ‘a’（所有 ‘a’ 组成的子序列 “aaa…a” 是回文）
    • 第二步：删除所有的 ‘b’（所有 ‘b’ 组成的子序列 “bbb…b” 是回文）

这是因为任何只包含相同字符的子序列都是回文的。比如所有的 ‘a’ 组成 “aaaa…"，所有的 ‘b’ 组成 “bbbb…"，这些都是回文序列。

所以算法非常简单：

  • 检查字符串是否为回文，如果是返回1
  • 否则返回2

时间复杂度： O(n) - 需要检查字符串是否为回文 空间复杂度： O(1) - 只使用常量额外空间

代码实现

class Solution {
public:
    int removePalindromeSub(string s) {
        // 检查字符串是否为回文
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return 2; // 不是回文，需要2步
            }
            left++;
            right--;
        }
        return 1; // 是回文，需要1步
    }
};

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        # 检查字符串是否为回文
        return 1 if s == s[::-1] else 2

public class Solution {
    public int RemovePalindromeSub(string s) {
        // 检查字符串是否为回文
        int left = 0, right = s.Length - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return 2; // 不是回文，需要2步
            }
            left++;
            right--;
        }
        return 1; // 是回文，需要1步
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var removePalindromeSub = function(s) {
    // 检查字符串是否为回文
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            return 2; // 不是回文，需要2步
        }
        left++;
        right--;
    }
    return 1; // 是回文，需要1步
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串检查是否为回文，n为字符串长度
空间复杂度O(1)只使用常量额外空间存储指针变量