> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1301-1400/remove-palindromic-subsequences.md).

# 1332. Remove Palindromic Subsequences

### Description

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.

### Constraints

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

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/remove-palindromic-subsequences/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** s = "ababa"

**Output:** 1

**Explanation:** String is already palindrome
{% endtab %}

{% tab title="Example 2" %}
**Input:** s = "abb"

**Output:** 2

**Explanation:** "abb" -> "bb" -> "".

Remove palindromic subsequence "a" then "bb".
{% endtab %}

{% tab title="Example 3" %}
**Input:** s = "baabb"

**Output:** 2

**Explanation:** "baabb" -> "b" -> "".

Remove palindromic subsequence "baab" then "b".
{% endtab %}

{% tab title="Example 4" %}
**Input:** s = ""

**Output:** 0
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n)
 * Space complexity : O(1)
 */

class Solution {
    public int removePalindromeSub(String s) {
        if(s.isEmpty()) {
            return 0;
        }
        return isPalindrome(s)? 1: 2;
    }
    
    private boolean isPalindrome(String s) {
        int left = 0, right = s.length()-1;
        while(left < right) {
            if(s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*