# Remove Palindromic Subsequences
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-palindromic-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/remove-palindromic-subsequences
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
---
## Problem
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'`.

# Approaches
## Palindrome Check via String Reversal
This approach hinges on the key observation that the problem can be simplified to determining if the input string is a palindrome. The string `s` consists only of 'a's and 'b's.

*   If `s` is already a palindrome, it can be removed in one step.
*   If `s` is not a palindrome, we can always remove all occurrences of 'a' as one palindromic subsequence, and then all occurrences of 'b' as a second palindromic subsequence. This is because a sequence of identical characters (like "aaaa" or "bbb") is always a palindrome. Therefore, any non-palindromic string can be cleared in exactly two steps.

This approach checks if the string is a palindrome by creating a reversed copy of the string and comparing it to the original.
**Time:** O(N), where N is the length of the string. Creating the reversed string using `StringBuilder` takes O(N) time, and comparing the two strings also takes O(N) time. · **Space:** O(N), as it requires extra space to store the reversed copy of the string.
**Pros:** Simple to understand and implement using built-in string manipulation functions.
**Cons:** Uses extra space that is proportional to the input string's length, which is less efficient than an in-place check.
### Explanation
The algorithm first handles the edge case of an empty string, which requires 0 steps. For non-empty strings, it creates a new string that is the reverse of the input string `s`. It then compares this new reversed string with the original string `s`. If they are equal, it means `s` is a palindrome, and the answer is 1. If they are not equal, `s` is not a palindrome, and based on our core logic, the answer is 2.

```java
class Solution {
    public int removePalindromeSub(String s) {
        if (s.isEmpty()) {
            return 0;
        }
        String reversedS = new StringBuilder(s).reverse().toString();
        if (s.equals(reversedS)) {
            return 1;
        } else {
            return 2;
        }
    }
}
```
### Algorithm
*   Check if the input string `s` is empty. If so, return 0.
*   Create a new string by reversing `s`.
*   Compare the original string `s` with the reversed string.
*   If they are identical, `s` is a palindrome. Return 1.
*   Otherwise, `s` is not a palindrome. Return 2.

## Optimized Palindrome Check using Two Pointers
This is the most efficient approach. It uses the same core logic as the previous method: the answer is 1 if the string is a palindrome, and 2 otherwise. The improvement comes from a more efficient way to check for a palindrome. Instead of creating a new reversed string, this method uses two pointers to check for palindromic properties in-place, which optimizes space usage.
**Time:** O(N), where N is the length of the string. In the worst case (the string is a palindrome), the two pointers traverse half of the string, resulting in N/2 comparisons. · **Space:** O(1), as it only uses a constant amount of extra space for the two pointer variables, regardless of the input size.
**Pros:** Highly efficient in terms of space complexity.; Often faster in practice for non-palindromes as it can exit early.
**Cons:** This is the optimal solution for this problem, so there are no significant cons.
### Explanation
The algorithm starts by handling the base case of an empty string. For non-empty strings, it initializes two pointers: `left` at the start of the string (index 0) and `right` at the end (index `s.length() - 1`). It then iterates while `left` is less than `right`, comparing the characters at these two pointers. If at any point the characters do not match, the string is not a palindrome, and we can immediately return 2. If the characters match, the pointers are moved inwards. If the loop completes without finding any mismatches, the string is a palindrome, and we return 1.

```java
class Solution {
    public int removePalindromeSub(String s) {
        if (s.isEmpty()) {
            return 0;
        }
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return 2; // Not a palindrome
            }
            left++;
            right--;
        }
        return 1; // Is a palindrome
    }
}
```
### Algorithm
*   Handle the base case: if the string `s` is empty, return 0.
*   Initialize two pointers: `left` at the beginning of the string (index 0) and `right` at the end (index `s.length() - 1`).
*   Iterate with a `while` loop as long as `left` is less than `right`.
*   Inside the loop, compare the characters at the `left` and `right` pointers.
*   If `s.charAt(left)` is not equal to `s.charAt(right)`, the string is not a palindrome. Return 2.
*   If the characters match, move the pointers closer to the center: increment `left` and decrement `right`.
*   If the loop finishes, the string is a palindrome. Return 1.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int removePalindromeSub(string s) {
    for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
      if (s[i] != s[j]) {
        return 2;
      }
    }
    return 1;
  }
};

```

### Python

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

```