Coders Packet

Palindromic subsequences using C++

By Savala Lingesh Reddy

Hello Coders, today we are going to solve the problem on palindrome using C++. Given a string we need to count the number of steps required to remove palindromic subsequences using C++.

The given string contains only 'a' and 'b' characters. Find the minimum number of steps required to make the given string empty.

A String is a palindrome when we read from the left it should be the same as when we read from the right (given string and its reverse should be equal.

Naive Approach :

  In the brute force method, palindromic subsequences can be removed by generating all the sub-strings. Start by removing a bigger substring and make a count of it. Time complexity is O(n2)

#include<bits/stdc++.h>
#include
using namespace std;
class Solution {
private:
    bool ispolin(string s,int i,int j){
        bool t = true;
        while(i < j){
            if(s[i] != s[j])
            {t = false;break;}
            i++;j--;
        }
        return t;
    }    
public:
    int removePalindromeSub(string s) {
        if(s.size() == 0)return 0;
        int l = 0,h = s.size()-1;
        bool f = ispolin(s,l,h);
        if(f)
            return 1;
        else return 2;
    }
};
int main(){
    Solution st;
    string str = "ababababa";
    int r = st.removePalindromeSub(str);
    cout<<r;
}

 

Optimized Approach :

  If we think about problem statements that, the given string contains only characters 'a' and 'b'. So if the given string itself is palindrome then the output is 1. Otherwise, the steps required are 2. By considering examples  ("ababab" , "babababa" , "bbaabba") etc.These examples require only 2 steps to make a given string empty.

 

Download project

Reviews Report

Submitted by Savala Lingesh Reddy (Lingesh)

Download packets of source code on Coders Packet