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) | | | | | | 1) | | | | | Returns: 3 | | The longest palindrome is "AVA". |
|
| | 2) | | | | | Returns: 0 | | The empty string is a palindrome of length 0. |
|
| | 3) | | | | "ONCEUPONATIMETHEREWASAYOUNGPROGRAMMERWHOLEARNED" | "TOPROGRAMJOINEDTOPCODERANDEVENTUALLYBECAMERED" |
| Returns: 9 | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
|
