Connection Status:
Competition Arena > InterleavePal

InterleavePal

SRM 305 · 2006-05-31 · by vorthys

SRM 305 · 2006-05-31 · by vorthys · Dynamic Programming, Search
Class Name: InterleavePal
Return Type: int
Method Name: longestPal
Arg Types: (string, string)
Problem Statement

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.

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)
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
Returns: 100
2)
""
"JAVA"
Returns: 3

The longest palindrome is "AVA".

3)
""
""
Returns: 0

The empty string is a palindrome of length 0.

4)
"ONCEUPONATIMETHEREWASAYOUNGPROGRAMMERWHOLEARNED"
"TOPROGRAMJOINEDTOPCODERANDEVENTUALLYBECAMERED"
Returns: 9

Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class InterleavePal with a public method int longestPal(string s, string t) · 84 test cases · 2 s / 256 MB per case

Submitting as anonymous