#1332
Remove Palindromic Subsequences
newbie · 280 · lc easy +20 · verified · 77% accepted · 1,745 likes · top 88%
Description
You have a string s made up only of 'a' and 'b'. In one step, remove any palindromic subsequence (not necessarily contiguous) from s. Return the minimum number of steps to empty s completely.
A palindrome reads identically forward and backward; a subsequence is formed by deleting some characters without changing the remaining order.
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".
Code
1
2
3