Question

1332. 删除回文子序列

English Version

题目描述

给你一个字符串 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 仅包含字母 'a'  和 'b'

解法

方法一：脑筋急转弯

如果字符串 $s$ 本身是个回文串，那么只需要删除 $1$ 次。

如果字符串 $s$ 不是个回文串，那么先删除所有的 'a'，再删除所有的 'b'，总共需要删除 $2$ 次。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$。

class Solution:
  def removePalindromeSub(self, s: str) -> int:
    return 1 if s[::-1] == s else 2

class Solution {
  public int removePalindromeSub(String s) {
    for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
      if (s.charAt(i) != s.charAt(j)) {
        return 2;
      }
    }
    return 1;
  }
}

class Solution {
public:
  int removePalindromeSub(string s) {
    for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
      if (s[i] != s[j]) {
        return 2;
      }
    }
    return 1;
  }
};

func removePalindromeSub(s string) int {
  for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
    if s[i] != s[j] {
      return 2
    }
  }
  return 1
}

function removePalindromeSub(s: string): number {
  for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
    if (s[i] !== s[j]) {
      return 2;
    }
  }
  return 1;
}

impl Solution {
  pub fn remove_palindrome_sub(s: String) -> i32 {
    let mut l = 0;
    let mut r = s.len() - 1;
    let s: Vec<char> = s.chars().collect();
    while l < r {
      if s[l] != s[r] {
        return 2;
      }
      l += 1;
      r -= 1;
    }
    1
  }
}