## DEV Community # Solution: Remove Palindromic Subsequences

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

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

#### Examples:

Example 1:
Input: s = "ababa"
Output: 1
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".
Example 4:
Input: s = ""
Output: 0

#### Constraints:

• `0 <= s.length <= 1000`
• `s` only consists of letters `'a'` and `'b'`

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The trick to this problem is realizing that since we're dealing with subsequences and only 2 possible characters, the answer cannot possible be larger than 2. In fact, the answer will always be 2 unless S is already a palindrome, in which case the answer is 1, or S is an empty string, in which case the answer is 0.

It's important to understand the distinction between a substring and a subsequence. A substring is a contiguous block of characters between one index and and another in the input string. A subsequence, which we're dealing with here, is any sequence of characters from the string, as long as they're in their original order. But you can pick and choose which characters you want in a subsequence, even if there are gaps between.

So in this situation I could, for example, create a subsequence of every single 'a' in the string. A string of all 'a' s would naturally be palindromic, so it could be removed from the original string. Since there are only 'a' s and 'b' s, that would leave only 'b' s remaining in the original string, which could be then removed in a second operation.

``````  S = "bbaabaaa"             // Input string
^^ ^^^              // Characters for the first subsequence
sub = "  aa aaa" = "aaaaa"   // Palindromic, so it can be removed
S = "bb  b   " = "bbb"     // Remaining string is palindromic and can be removed
``````

#### Implementation:

Python can more easily just compare the string with its reverse self via index access shorthand.

#### Javascript Code:

``````var removePalindromeSub = function(S) {
if (!S) return 0
for (let i = 0, j = S.length - 1; i < j; i++, j--)
if (S.charAt(i) !== S.charAt(j)) return 2
return 1
};
``````

#### Python Code:

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

#### Java Code:

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

#### C++ Code:

``````class Solution {