Remove Palindromic Subsequences Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions StringViews 2631

The problem Remove Palindromic Subsequences Leetcode Solution states that you are given a string. The string consists of only two characters ‘a’ or ‘b’. You are required to erase the whole string. There is a restriction that you can delete only a palindromic subsequence in one move. Find the minimum number of steps required to erase the whole string. Let us take a look at a few examples before jumping into the solution.

Remove Palindromic Subsequences Leetcode Solution

s = "ababa"
1

Explanation: Since the string is a palindrome. We can remove the whole string in a single move. Thus the answer is also 1.

s = "abb"
2

Explanation: In the first move, we remove “bb”. In the second move, we remove “a”. Thus we require at least 2 moves to erase the whole string.

Approach for Remove Palindromic Subsequences Leetcode Solution

The problem Remove Palindromic Subsequences Leetcode Solution is an observation one. It requires us to observe that the string consists of only two characters ‘a’ and ‘b’. If we come across a palindrome, we simply return 1. Because it requires a single move to erase a whole palindrome. If we get an empty string, we should return 0. But other than these, there is only a single case, when we have a string that is not palindrome as a whole.

But since the string has only ‘a’ and ‘b’. We will take at most 2 moves to remove all the characters. In the first move, we should remove all ‘a’s. In the second move, we remove all ‘b’s. Thus the answer to this p[problem can be only 0, 1, or 2 depending on the input.

Code to Remove Palindromic Subsequences Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

int removePalindromeSub(string s) {
    if(s.size() == 0)
        return 0;

    // check if palindrome
    bool isPalin = true;
    for(int i=0;i<s.length()/2;i++)
        if(s[i] != s[s.length()-1-i])
            isPalin = false;

    if(isPalin == true)
        return 1;
    else
        return 2;
}

int main(){
    cout<<removePalindromeSub("abb");
}

2

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int removePalindromeSub(String s) {
        if(s.isEmpty())
            return 0;
        
        // check if palindrome
        boolean isPalin = true;
        for(int i=0;i<s.length()/2;i++)
            if(s.charAt(i) != s.charAt(s.length()-1-i))
                isPalin = false;
        
        if(isPalin == true)
            return 1;
        else
            return 2;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(removePalindromeSub("abb"));
  }
}
2

Complexity Analysis

Time Complexity

O(N), because we need to go through the entire string to check if it’s palindrome or not.

Space Complexity

O(1), because we use a constant number of variables.

Translate »