1332. Remove Palindromic Subsequences

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: “abb” -> “bb” -> “”.
Remove palindromic subsequence “a” then “bb”.

Example 3:

Input: s = “baabb”
Output: 2
Explanation: “baabb” -> “b” -> “”.
Remove palindromic subsequence “baab” then “b”.

Constraints:

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

``````class Solution {
public:
int removePalindromeSub(string s) {
if (s.empty()) return 0;
return isPalindrome(s) ? 1 : 2;
}
bool isPalindrome(string s) {
int left = 0, right = (int)s.size() - 1;
while (left < right) {
if (s[left] != s[right]) return false;
++left; --right;
}
return true;
}
};
``````

``````class Solution {
public:
int removePalindromeSub(string s) {
return 2 - (string(s.rbegin(), s.rend()) == s) - s.empty();
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1332

https://leetcode.com/problems/remove-palindromic-subsequences/

https://leetcode.com/problems/remove-palindromic-subsequences/solutions/490303/java-c-python-maximum-2-operations/

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation