Longest Palindrome After Substring Concatenation I

Longest Palindrome After Substring Concatenation I - 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.

A palindrome is a string that reads the same forwards and backwards.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Select substring "a" from s and "ba" from t to form "aba", which is a palindrome of length 3. This is the maximum possible.

Example 2 — Single Character

$ Input: s = "x", t = "y"

› Output: 1

💡 Note: Best we can do is select "x" from s (and empty from t) or "y" from t (and empty from s), giving palindromes of length 1.

Example 3 — Identical Strings

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

› Output: 3

💡 Note: Select "a" from s and "bc" from t to get "abc", or "ab" from s and "c" from t to get "abc". Neither is palindrome. Best is single characters like "a", "b", or "c" with length 1, but "cac" from "c"+"a"+"c" isn't valid since we need s+t order. Actually "aba" can be formed by selecting "ab" from s and "a" from t... wait, that gives "aba" which works! Length 3.

Constraints

0 ≤ 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 with potential substrings

Combine Substrings

Select substring from s + substring from t

Find Longest Palindrome

Return maximum length palindrome possible

Key Takeaway

🎯 Key Insight: Every palindrome can be formed by carefully selecting complementary substrings from both input strings

Asked in

G Google 25 a Amazon 18 f Meta 15 M Microsoft 12

The key insight is to systematically try all possible substring combinations from both strings and check for palindromes. The brute force approach works by generating all substrings from s and t, concatenating them, and checking if each result is a palindrome. Best approach is brute force enumeration with Time: O(n²m²(n+m)), Space: O(n+m).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers with Boundary Tracking	O(n²m²)	O(1)	Use two pointers to efficiently check palindrome candidates
Expand Around Centers	O(n²m²)	O(1)	Expand around potential palindrome centers more efficiently
Brute Force Enumeration	O(n²m²(n+m))	O(n+m)	Try all possible substring combinations from both strings

Two Pointers with Boundary Tracking — Algorithm Steps

Step 1: For each possible boundary between s and t portions
Step 2: Use left and right pointers to check palindrome property
Step 3: Ensure pointers respect s/t boundaries during expansion
Step 4: Track maximum valid palindrome length

Visualization

Tap to expand

Step-by-Step Walkthrough

Combine Strings

Concatenate selected substrings from s and t

Two Pointers Check

Use left/right pointers to verify palindrome

Update Maximum

Track longest valid palindrome found

Code -

solution.c — C

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

int isPalindromeTwoPointers(const char* leftStr, const char* rightStr) {
    char combined[2001];
    strcpy(combined, leftStr);
    strcat(combined, rightStr);
    
    int left = 0, right = strlen(combined) - 1;
    while (left < right) {
        if (combined[left] != combined[right]) {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}

int solution(const char* s, const char* t) {
    int maxLength = 0;
    int n = strlen(s), m = strlen(t);
    char sSub[1001], tSub[1001];
    
    // Try all possible substrings from s and t
    for (int i = 0; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            strncpy(sSub, s + i, j - i);
            sSub[j - i] = '\0';
            
            for (int x = 0; x <= m; x++) {
                for (int y = x; y <= m; y++) {
                    strncpy(tSub, t + x, y - x);
                    tSub[y - x] = '\0';
                    
                    if (isPalindromeTwoPointers(sSub, tSub)) {
                        int length = strlen(sSub) + strlen(tSub);
                        if (length > maxLength) {
                            maxLength = length;
                        }
                    }
                }
            }
        }
    }
    
    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²m²) combinations with O(1) palindrome check per combination

⚠ Quadratic Growth

Space Complexity

O(1)

Only using pointer variables, no extra data structures

✓ Linear Space

30.3K Views

Medium Frequency

~25 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

Two Pointers with Boundary Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler