Maximize Palindrome Length From Subsequences

Maximize Palindrome Length From Subsequences - Problem

You are given two strings, word1 and word2. You want to construct a string in the following manner:

Choose some non-empty subsequence subsequence1 from word1.
Choose some non-empty subsequence subsequence2 from word2.
Concatenate the subsequences: subsequence1 + subsequence2, to make the string.

Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.

A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.

A palindrome is a string that reads the same forward as well as backward.

Input & Output

Example 1 — Basic Case

$ Input: word1 = "cacb", word2 = "cbba"

› Output: 5

💡 Note: Choose subsequence "ab" from word1 and "cba" from word2 to form "abcba" which is a palindrome of length 5

Example 2 — Simple Match

$ Input: word1 = "ab", word2 = "ba"

› Output: 3

💡 Note: Choose "ab" from word1 and "a" from word2 to get "aba", or "a" from word1 and "ba" from word2 to get "aba"

Example 3 — No Valid Palindrome

$ Input: word1 = "aa", word2 = "bb"

› Output: 0

💡 Note: Cannot form a palindrome that uses characters from both strings - "aab", "abb", "aabb" are not palindromes

Constraints

1 ≤ word1.length, word2.length ≤ 1000
word1 and word2 consist of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings word1 and word2

Process

Find subsequences from each that form longest palindrome when concatenated

Output

Length of longest valid palindrome

Key Takeaway

🎯 Key Insight: The challenge is finding subsequences from each string that form the longest palindrome when concatenated, requiring both strings to contribute at least one character.

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to combine both strings and use dynamic programming to find the longest palindromic subsequence while ensuring characters from both original strings are included. Best approach uses memoized recursion with constraint tracking. Time: O((m+n)²), Space: O((m+n)²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsequences	O(2^(m+n) × (m+n))	O(2^(m+n) × (m+n))	Generate all possible subsequences from both strings and check palindromes
Dynamic Programming - Extended LPS	O((m+n)²)	O((m+n)²)	Combine strings and use 2D DP to find longest palindromic subsequence with constraints

Brute Force - Try All Subsequences — Algorithm Steps

Step 1: Generate all subsequences of word1
Step 2: Generate all subsequences of word2
Step 3: For each pair, concatenate and check if palindrome
Step 4: Return maximum palindrome length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsequences

Create all possible subsequences from both strings

Combine & Check

Concatenate pairs and test for palindromes

Track Maximum

Keep the longest palindrome length found

Code -

solution.c — C

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

bool isPalindrome(char* s) {
    int left = 0, right = strlen(s) - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int solution(char* word1, char* word2) {
    int n1 = strlen(word1);
    int n2 = strlen(word2);
    int maxLen = 0;
    
    for (int mask1 = 1; mask1 < (1 << n1); mask1++) {
        for (int mask2 = 1; mask2 < (1 << n2); mask2++) {
            char subseq1[1001] = {0};
            char subseq2[1001] = {0};
            char combined[2002] = {0};
            
            int idx1 = 0, idx2 = 0;
            for (int i = 0; i < n1; i++) {
                if (mask1 & (1 << i)) {
                    subseq1[idx1++] = word1[i];
                }
            }
            for (int i = 0; i < n2; i++) {
                if (mask2 & (1 << i)) {
                    subseq2[idx2++] = word2[i];
                }
            }
            
            strcpy(combined, subseq1);
            strcat(combined, subseq2);
            
            if (isPalindrome(combined)) {
                int len = strlen(combined);
                if (len > maxLen) {
                    maxLen = len;
                }
            }
        }
    }
    
    return maxLen;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(2^(m+n) × (m+n))

2^m subsequences from word1, 2^n from word2, O(m+n) to check each palindrome

✓ Linear Growth

Space Complexity

O(2^(m+n) × (m+n))

Store all subsequences and concatenated strings

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

890 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

Brute Force - Try All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler