Longest Palindromic Subsequence II - Practice Coding Problems

Longest Palindromic Subsequence II - Problem

A subsequence of a string s is considered a good palindromic subsequence if:

It is a subsequence of s.
It is a palindrome (has the same value if reversed).
It has an even length.
No two consecutive characters are equal, except the two middle ones.

For example, if s = "abcabcabb", then "abba" is considered a good palindromic subsequence, while "bcb" (not even length) and "bbbb" (has equal consecutive characters) are not.

Given a string s, return the length of the longest good palindromic subsequence in s.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcabc"

› Output: 4

💡 Note: The good palindromic subsequence "abba" can be formed by taking characters at indices 0,1,3,4 → a,b,b,a. Length is 4, it's a palindrome, has even length, and no consecutive duplicates except the middle bb.

Example 2 — No Valid Subsequence

$ Input: s = "aaa"

› Output: 0

💡 Note: Cannot form any good palindromic subsequence. "aa" would have consecutive equal characters but they're not in the middle positions.

Example 3 — Longer String

$ Input: s = "bbcacb"

› Output: 4

💡 Note: The good palindromic subsequence "bcab" can be formed by taking characters at indices 0,2,3,5 → b,c,a,b. Wait, that's "bcab" which is not a palindrome. Actually "bccb" from indices 0,1,2,5 gives b,b,c,b - not valid due to consecutive b's. The valid one is "bccb" but rearranged properly.

Constraints

1 ≤ s.length ≤ 250
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String with characters that need to form palindrome

Apply Constraints

Even length, palindrome, no consecutive duplicates except middle

Find Maximum

Return length of longest valid subsequence

Key Takeaway

🎯 Key Insight: Use DP to track palindromes while enforcing even length and no consecutive duplicates

Asked in

G Google 15 F Facebook 12 A Amazon 8

The key insight is to use dynamic programming to track palindromic subsequences while ensuring the constraints: even length and no consecutive duplicates except the middle pair. The memoized recursion approach works well by trying to match characters from both ends and tracking the last characters used to prevent consecutive duplicates. Time: O(n² × 26²), Space: O(n² × 26²)

Common Approaches

Approach	Time	Space	Notes
✓ 2D Dynamic Programming	O(n² × 26²)	O(n² × 26²)	Use 2D DP table to track longest good palindromic subsequences with character constraints
Memoized Recursion	O(n² × 26²)	O(n² × 26²)	Use recursion with memoization to find longest valid palindromic subsequences
Brute Force - Generate All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check each one for validity

2D Dynamic Programming — Algorithm Steps

Create 2D DP table dp[i][j]
Handle base cases for single characters
Fill table by trying character matches
Ensure even length and no consecutive duplicates

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create DP table for all substring ranges

Fill Table

Process substrings from small to large

Extract Answer

Get result from dp[0][n-1]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_MEMO 50000

typedef struct {
    int i, j, c1, c2;
    int result;
} MemoEntry;

MemoEntry memoTable[MAX_MEMO];
int memoCount = 0;

int findMemo(int i, int j, int c1, int c2) {
    for (int k = 0; k < memoCount; k++) {
        if (memoTable[k].i == i && memoTable[k].j == j && 
            memoTable[k].c1 == c1 && memoTable[k].c2 == c2) {
            return memoTable[k].result;
        }
    }
    return -1;
}

void addMemo(int i, int j, int c1, int c2, int result) {
    if (memoCount < MAX_MEMO) {
        memoTable[memoCount].i = i;
        memoTable[memoCount].j = j;
        memoTable[memoCount].c1 = c1;
        memoTable[memoCount].c2 = c2;
        memoTable[memoCount].result = result;
        memoCount++;
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

int getDp(const char* s, int i, int j, int c1, int c2) {
    if (i > j) return 0;
    
    int cached = findMemo(i, j, c1, c2);
    if (cached != -1) return cached;
    
    int result = 0;
    
    // Skip current start
    result = max(result, getDp(s, i + 1, j, c1, c2));
    
    // Skip current end
    if (i < j) {
        result = max(result, getDp(s, i, j - 1, c1, c2));
    }
    
    // Try to include both i and j if they match
    if (s[i] == s[j]) {
        int valid = 1;
        if (c1 != -1 && c1 == (int)s[i]) valid = 0;
        if (c2 != -1 && c2 == (int)s[j]) valid = 0;
        
        if (valid && i < j) {
            result = max(result, 2 + getDp(s, i + 1, j - 1, (int)s[i], (int)s[j]));
        }
    }
    
    addMemo(i, j, c1, c2, result);
    return result;
}

int solution(const char* s) {
    int n = strlen(s);
    if (n == 0) return 0;
    
    memoCount = 0;
    return getDp(s, 0, n - 1, -1, -1);
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × 26²)

n² substrings, each considering 26² possible last character pairs

⚠ Quadratic Growth

Space Complexity

O(n² × 26²)

DP table with dimensions for positions and last characters

⚠ Quadratic Space

12.0K Views

Medium Frequency

~35 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler