Find the longest palindrome that can be formed by concatenating a substring from one string and a substring from another string.
Given two strings, choose one substring from each string and concatenate them in order. Your task is to maximize the length of a palindrome that can be formed this way.
A substring must be contiguous, and the two chosen substrings may be empty only if needed by the formulation of the specific instance. The goal is to return the length of the longest palindromic string obtainable by combining a substring from the first string with a substring from the second string.
Input Format
- Two strings
sandt. - Each string consists of lowercase English letters.
- You may choose a contiguous substring from
sand a contiguous substring fromt, then concatenate them assubstring(s) + substring(t). - Return the maximum palindrome length possible.
Output Format
- Return a single integer: the maximum length of a palindrome that can be formed by concatenating one substring from each input string.
Constraints
- Strings contain only lowercase English letters.
- Substrings must be contiguous.
- The answer is the length of the longest valid palindrome.
- Exact official limits are not provided here; assume interview-scale inputs.
Example 1
Input
s = "ab", t = "ba"
Output
4
Explanation
Choose substring(s) = "ab" and substring(t) = "ba". Their concatenation is "abba", which is a palindrome of length 4.
Example 2
Input
s = "abc", t = "cba"
Output
6
Explanation
Choose "abc" from the first string and "cba" from the second string. The concatenation "abccba" is a palindrome.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.