1332. 删除回文子序列

🟢   🔖  双指针 字符串  🔗 力扣 LeetCode

题目

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"

Output: 1

Explanation: s is already a palindrome, so its entirety can be removed in a single step.

Example 2:

Input: s = "abb"

Output: 2

Explanation: "a bb" -> "bb " -> "".

Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"

Output: 2

Explanation: "baa b b " -> "b " -> "".

Remove palindromic subsequence "baab" then "b".

Constraints:

• 1 <= s.length <= 1000
• s[i] is either 'a' or 'b'.

题目大意

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

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

「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。

「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。

示例 1：

输入： s = "ababa"

输出： 1

解释： 字符串本身就是回文序列，只需要删除一次。

示例 2：

输入： s = "abb"

输出： 2

解释： "a bb" -> "bb " -> "".

先删除回文子序列 "a"，然后再删除 "bb"。

示例 3：

输入： s = "baabb"

输出： 2

解释： "baa bb " -> "b" -> "".

先删除回文子序列 "baab"，然后再删除 "b"。

提示：

• 1 <= s.length <= 1000
• s 仅包含字母 'a' 和 'b'

解题思路

1. 如果字符串 s 本身就是回文，那么只需要移除一次子序列即可（直接移除整个字符串）。

2. 如果 s 不是回文字符串，则最少只需要进行两次移除操作：

   • 先移除所有的 a，然后移除所有的 b

3. 特殊情况： 当字符串 s 为空时，直接返回 0，因为没有子序列可移除。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度，在判断回文时需要遍历字符串的一半。
• 空间复杂度：O(1)，只用了常数的额外空间。

代码

/**
 * @param {string} s
 * @return {number}
 */
var removePalindromeSub = function (s) {
	const isPalindrome = (s) => {
		let left = 0,
			right = s.length - 1;
		while (left < right) {
			if (s[left] !== s[right]) return false;
			left++;
			right--;
		}
		return true;
	};

	// 空字符串直接返回 0
	if (s.length == 0) return 0;
	// 如果字符串本身是回文，返回 1
	if (isPalindrome(s)) return 1;
	// 否则返回 2
	return 2;
};