Problem Statement | |||||||||||||
A palindrome is a sequence of letters that reads the same forwards and backwards, such as "MOM".
Given two Strings, s and t, you are to find the length of the longest palindrome that is a contiguous substring of some interleaving of s and t. For example, the strings "AA" and "BB" can be interleaved in six ways:
AABB BBAA ABAB BABA ABBA BAABOf these, the top two contain palindromes of length 2 ("AA" and "BB"), the middle two contain palindromes of length 3 ("ABA" and "BAB"), and the bottom two contain palindromes of length 4 ("ABBA" and "BAAB"), so the answer would be 4. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | To interleave two strings, you intersperse their characters. For example, "ABCDE" is one way to interleave the strings "ACE" and "BD". However, the characters need not strictly alternate between the two strings. For example, "BACED" and "ACBDE" are also ways to interleave the strings "ACE" and "BD". Notice that the characters from the original strings maintain their order with respect to other characters from the same string (e.g., the 'B' always comes before the 'D' in the above examples). | ||||||||||||
| - | Interleaving any string with the empty string yields the original string. | ||||||||||||
Constraints | |||||||||||||
| - | s will contain between 0 and 50 characters, inclusive. | ||||||||||||
| - | t will contain between 0 and 50 characters, inclusive. | ||||||||||||
| - | Every character in s will be an uppercase letter ('A'-'Z'). | ||||||||||||
| - | Every character in t will be an uppercase letter ('A'-'Z'). | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||