Leetcode 1332: Remove Palindromic Subsequences [Solution]
Tags: algorithms, cpp, leetcode, programming
Published: 2021-03-08 15:37:03

The answer to this question is way simpler than the question itself, it took much time to understand the question for me at least. But once you get the question, I am sure you'll get the answer by yourself.

**Difficulty:** Easy
**Jump To:**
* [Problem Statement](#problem-statement)
* [Explanation](#explanation)
* [Solution](#solution)
* [Implementation](#implementation)

---

## Problem Statement <a name="problem-statement"></a>
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.

 

**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
 

**Constraints:**

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

---

## Explanation <a name="explanation"></a>
*Did you get the question?* If yes, then you are a PRO, if not then don't worry, you are normal, like me. So before understanding the question, let's first understand what are **subsequence** and **palindrome**.
* **Subsequence:** A string is a [subsequence](https://en.wikipedia.org/wiki/Subsequence) of a given string if it is generated by deleting some characters of a given string without changing its order. **eg.** for string `shivam`, `ham` is a substring after deleting `s`, `i` and `v`.
* **Substring:** Don't confuse *subsequence* with *[substring](https://en.wikipedia.org/wiki/Substring)*. A substring is a contiguous sequence of characters within a string. **eg.** for string `shivam`, `iva` is a substring while `ham` is not. So it's clear that *"All substrings are subsequences as well but not vice versa."*
* **Palindrome:** A [palindrome](https://en.wikipedia.org/wiki/Palindrome) is a word, number, phrase, or other sequences of characters which reads the same backward as forward, such as `madam` or `racecar`.

So the question wants to say that you can remove any subsequence from the string if it's a palindrome and the goal is to find that how many such deletion operations are needed to make the string empty.
Before going to the solution, do you want to see some hints? Here they are:
1. Use the fact that the string contains only 2 characters.
2. Are subsequences composed of only one type of letter always palindrome strings?

---

## Solution <a name="solution"></a>
We are going to use the below ideas to solve this question:
1. If any string is empty, then we don't need to do anything and return `0`.
2. If a string is a palindrome then we can delete the whole string in a single operation as a string is also a subsequence of itself. For such case, we need to return `1`.
3. A string of any length consists of a single type of character is always a subsequence **eg.** `aaaaa`, `bbb`, `a` etc.
4. So, I can delete a subsequence containing all characters of the same type from the string. **eg.** from string `aaabbbababa` I can remove `aaaaaa` as it's a subsequence and palindrome as well.
5. And surprise, we are left with the string `bbbbb` which is also a palindrome so we can delete this in a single operation.
6. As the string can contain only `'a'` or `'b'` only. So if the string is not palindrome then I can delete all the `'a'`s in the first pass then all the `'b'`s in the second pass, so the max operations we need is `2` if the string is not a palindrome.

---

## Implementation <a name="implementation"></a>

**C++ Code:**

```cpp
class Solution {
public:
	int removePalindromeSub(string s) {
		// Check if string is empty
		if(s.empty())
			return 0;

		int len=s.size();

		// Check for pallindrome
		for(int i=0; i<=len/2; i++){
			// If not pallindrome then 2 operations are needed
			if(s[i] != s[len-i-1])
				return 2;
		}
		// If pallindrome then only one operation is needed
		return 1;
	}
};
```

**Runnable C++ Code:**
{% replit @shivams136/Leetcode-1332-Remove-Pallindromic-Subsequence %}