Palindrome From Two Pieces

Hard

You are given two strings first and second. Cut a contiguous piece (possibly empty) out of first and a contiguous piece (possibly empty) out of second, then glue the second piece onto the right end of the first. Return the greatest length of a palindrome you can build this way. A palindrome reads the same left to right and right to left.

Example 1

first='xbat', second='tabz' → 6

Take "bat" from first and "tab" from second to get "battab", length 6.

Example 2

first='qq', second='rstsr' → 5

The piece of first may be empty: all of "rstsr" is a palindrome of length 5.

Example 3

first='abc', second='xyz' → 1

The strings share no letters, so the best is a single letter.

Constraints

1 ≤ len(first), len(second) ≤ 1000
Both strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Input

first='xbat', second='tabz'

Expected

Run checks the first 3 tests in your browser. Submit checks all 124 tests on the server, hidden ones included.