Remove Palindromic Subsequences

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:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".

Approach:

C++

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

bool isPalindrome(string s)
{
    int low = 0high = s.size() - 1;
    while (low < high)
    {
        if (s[low] != s[high])
            return false;
        low++;
        high--;
    }
    return true;
}
int removePalindromeSub(string s)
{
    if (s.size() == 0)
        return 0;
    if (isPalindrome(s))
        return 1;
    return 2;
}

int main()
{
    string s = "abb";

    cout << removePalindromeSub(s);
    return 0;
}


No comments:

Post a Comment