Leetcode 1332: Remove Palindromic Subsequences [Solution]

#algorithms #cpp #leetcode #programming

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
Explanation
Solution
Implementation

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.

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

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 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. 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 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:

Use the fact that the string contains only 2 characters.
Are subsequences composed of only one type of letter always palindrome strings?

Solution

We are going to use the below ideas to solve this question:

If any string is empty, then we don't need to do anything and return 0.
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.
A string of any length consists of a single type of character is always a subsequence eg. aaaaa, bbb, a etc.
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.
And surprise, we are left with the string bbbbb which is also a palindrome so we can delete this in a single operation.
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

C++ Code:

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;
    }
};