### 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    BAAB
Of 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

 Class: InterleavePal Method: longestPal Parameters: String, String Returns: int Method signature: int longestPal(String s, String t) (be sure your method is public)

### 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)

 "AA" "BB"
Returns: 4
 The example above.
1)

 "" "JAVA"
Returns: 3
 The longest palindrome is "AVA".
2)

 "" ""
Returns: 0
 The empty string is a palindrome of length 0.
3)

 "ONCEUPONATIMETHEREWASAYOUNGPROGRAMMERWHOLEARNED" "TOPROGRAMJOINEDTOPCODERANDEVENTUALLYBECAMERED"
Returns: 9

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6435

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9826&pm=6435

vorthys

#### Testers:

PabloGilberto , Olexiy , lovro , Andrew_Lazarev

#### Problem categories:

Dynamic Programming, Search