Longest Palindrome After Substring Concatenation II

Longest Palindrome After Substring Concatenation II - Problem

You are given two strings, s and t. You can create a new string by selecting a substring from s (possibly empty) and a substring from t (possibly empty), then concatenating them in order.

Return the length of the longest palindrome that can be formed this way.

Note: A palindrome is a string that reads the same forward and backward. An empty string is considered a palindrome of length 0.

Input & Output

Example 1 — Basic Case

$ Input: s = "abc", t = "cba"

› Output: 6

💡 Note: Take full string from s ("abc") and full string from t ("cba") to form "abccba", which is a palindrome of length 6

Example 2 — Partial Substrings

$ Input: s = "ab", t = "ba"

› Output: 4

💡 Note: Take "ab" from s and "ba" from t to form "abba", which is a palindrome of length 4

Example 3 — Empty Substring

$ Input: s = "abc", t = "def"

› Output: 1

💡 Note: No good concatenation forms a long palindrome. Best is taking single character like "a" (from s) + "" (empty from t) = "a" with length 1

Constraints

1 ≤ s.length, t.length ≤ 1000
s and t consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings s and t from which we select substrings

Concatenate

Combine substring from s with substring from t

Find Maximum

Return length of longest palindrome possible

Key Takeaway

🎯 Key Insight: We need to systematically try different substring combinations to find the longest possible palindrome

Asked in

G Google 35 f Facebook 28 a Amazon 22

The key insight is that we need to find the optimal way to concatenate substrings from two strings to form the longest palindrome. The brute force approach tries all possible combinations but is slow. The dynamic programming approach provides a more systematic solution by building up results for all prefix combinations. Time: O(n×m×(n+m)), Space: O(n×m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n³ × m³)	O(n + m)	Generate all possible concatenations and check if they form palindromes
Dynamic Programming Solution	O(n × m × (n + m))	O(n × m)	Use 2D DP to store results of subproblems and build optimal solution
Two Pointers Optimization	O(n² × m²)	O(1)	Use two pointers to efficiently check palindrome properties while building concatenations

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all substrings of s (including empty)
Step 2: Generate all substrings of t (including empty)
Step 3: For each pair, concatenate and check if palindrome
Step 4: Track maximum length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings from both strings

Concatenate & Check

Combine each pair and test if palindrome

Track Maximum

Keep track of longest palindrome found

Code -

solution.c — C

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

int isPalindrome(const char* str) {
    int len = strlen(str);
    int left = 0, right = len - 1;
    while (left < right) {
        if (str[left] != str[right]) {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}

int solution(char* s, char* t) {
    int maxLength = 0;
    int n = strlen(s), m = strlen(t);
    char* combined = malloc(n + m + 1);
    
    // Try all substrings of s
    for (int i = 0; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            // Try all substrings of t
            for (int k = 0; k <= m; k++) {
                for (int l = k; l <= m; l++) {
                    // Build combined string
                    int pos = 0;
                    for (int p = i; p < j; p++) {
                        combined[pos++] = s[p];
                    }
                    for (int p = k; p < l; p++) {
                        combined[pos++] = t[p];
                    }
                    combined[pos] = '\0';
                    
                    if (isPalindrome(combined)) {
                        int len = strlen(combined);
                        if (len > maxLength) {
                            maxLength = len;
                        }
                    }
                }
            }
        }
    }
    
    free(combined);
    return maxLength;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n³ × m³)

O(n²) substrings from s, O(m²) from t, O(n+m) to check each palindrome

⚠ Quadratic Growth

Space Complexity

O(n + m)

Space to store concatenated strings for palindrome checking

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 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 Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler