#
**PROBLEM STATEMENT**

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.

#
**TEST CASES**

Example 1:

Input: s = "ababa"

Output: 1

Explanation: String is already palindrome

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

#
**IDEA**

Before getting on to the main problem, lets understand what is a subsequence and what is a substring.

Subsequence - A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements.

For the same example, there are 15 sub-sequences. They are (1), (2), (3), (4), (1,2), (1,3),(1,4), (2,3), (2,4), (3,4), (1,2,3), (1,2,4), (1,3,4), (2,3,4), (1,2,3,4). More generally, we can say that for a sequence of size n, we can have (2^n-1) non-empty sub-sequences in total.

Substring - A subbarray is a contiguous part of array. An array that is inside another array. For example, consider the array [1, 2, 3, 4], There are 10 non-empty sub-arrays. The subbarays are (1), (2), (3), (4), (1,2), (2,3), (3,4), (1,2,3), (2,3,4) and (1,2,3,4). In general, for an array/string of size n, there are n*(n+1)/2 non-empty subarrays/subsrings.

So now coming to our problem, we need to remove palindromic subsequence to make the string empty and we are having only 2 letters a and b. This made to a conclusion that we have 3 options:

**1)** Given string is empty, so return 0.

**2)** Given string is already palindrome, so remove the whole string which makes the step = 1. So just return 1.

**3) Given string is not palindrome, then consider removing 'a' or 'b' as the first step of remove. In this step we remove the complete 'a' and as a second step we remove the remaining letters 'a' or 'b'. So return 2 this time.

And this gives our whole problem.

#
**ALGORITHM:**

1) Check if given string empty, if true return 0.

2) Take 2 pointers left = 0, right = stringLength - 1

3) while left < right, do the following

-> check for palindromic condition, if fails return 2 else continue until the loops gets over.

4) return 1.

#
**CODE**

```
// here there are 3 conditions that we want to consider
// 1. if the string is empty, then return 0. This can be our first check.
// 2. Next one is checking palindrome or not. If the whole string is palindrome, then we can delete it completely. So return 1.
// 3. The next one is either we can remove a completely then b or vice versa. So in this case number of steps will be only 2.
// That is first step can be to remove all 'a's and the second step is remove all 'b's.
class Solution {
public int removePalindromeSub(String s) {
// string empty
if (s.length() == 0)
return 0;
int left = 0;
int right = s.length() - 1;
while (left < right) {
// palindrome condition
if (s.charAt(left) == s.charAt(right)) {
left += 1;
right -= 1;
}
else
return 2;
}
return 1;
}
}
```

**TIME COMPLEXITY:** **SPACE COMPLEXITY**:

O(lengthOfString) O(1)

**GITHUB LINK**:Link

## Discussion (0)