- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose, we are given a string. We have to find out a palindromic subsequence that is of even length and does not contain two consecutive same characters except in the middle. We have to return the length of this type of substrings as output.

So, if the input is like s = 'efeffe', then the output will be 4

The output is 4 because there is only one palindromic subsequence that is of even length. The string is 'effe' that is of length 4.

To solve this, we will follow these steps −

n := size of s

dp := one n x n 2d array where each item is a pair in the form (0, blank string)

for i in range n-1 to -1, decrease by 1, do

for j in range i+1 to n, do

if s[i] is same as s[j] and string of dp[i+1, j-1] is not s[i], then

dp[i, j] := make a pair (first element of dp[i+1, j-1] + 2, s[i])

otherwise,

dp[i, j] := select among (dp[i+1, j], dp[i, j-1], dp[i+1,j-1]) for which first element of pair is maximum

return first element of pair stored at dp[0, n-1]

Let us see the following implementation to get better understanding −

def solve(s): n = len(s) dp = [[(0, '')]*n for _ in range(n)] for i in range(n-1, -1, -1): for j in range(i+1, n): if s[i]== s[j] and dp[i+1][j-1][1] != s[i]: dp[i][j] = (dp[i+1][j-1][0] + 2, s[i]) else: dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0]) return dp[0][n-1][0] print(solve('efeffe'))

'efeffe'

4

- Related Questions & Answers
- Program to find length of longest palindromic subsequence in Python
- Program to find length of longest palindromic substring in Python
- Longest Palindromic Subsequence
- Program to find length of longest balanced subsequence in Python
- Program to find length of longest anagram subsequence in Python
- Program to find length of longest increasing subsequence in Python
- Java Program for Longest Palindromic Subsequence
- Program to find length of longest circular increasing subsequence in python
- Program to find length of longest palindromic substring after single rotation in Python
- Program to find length of longest common subsequence in C++
- Program to find length of longest bitonic subsequence in C++
- Longest Palindromic Subsequence in C++
- Program to find length of longest common subsequence of three strings in Python
- Program to find length of longest arithmetic subsequence of a given list in Python
- Program to find length of longest Fibonacci subsequence from a given list in Python

Advertisements