TopCoder problem "PalindromeGame" used in SRM 499 (Division II Level Three)

Problem Statement

    You are playing a simple one-player game in which you are given a set of cards. Each card has a string written on the front and a number on the back. The strings on all the cards have the same length. You must choose some of these cards (at least one, possibly all) and place them in a row with the front sides visible, such that the concatenated string is a palindrome. A palindrome is a string that reads the same forward and backward. Your score is the sum of the numbers on the back sides of the chosen cards.

You are given a String[] front and a int[] back describing the set of cards you are given. The i-th card has front[i] written on the front and back[i] on the back. Return the maximum possible score you can achieve with these cards. If it is impossible to compose a palindrome from the given cards, return 0 instead.


Parameters:String[], int[]
Method signature:int getMaximum(String[] front, int[] back)
(be sure your method is public)


-front will contain between 1 and 50 elements, inclusive.
-Each element of front will contain between 1 and 50 characters, inclusive.
-Each element of front will contain the same number of characters.
-Each character in front will be a lowercase letter ('a' - 'z').
-front and back will contain the same number of elements.
-Each element of back will be between 1 and 1,000,000, inclusive.


{ "topcoder", "redcoder", "redocpot" }
{ 7, 5, 3 }
Returns: 10
You can choose "topcoder" with 7 and "redocpot" with 3 to get a palindrome "topcoderredocpot".
{ "rabbit" }
{ 1000000 }
Returns: 0
No palindrome can be made.
{ "abc", "abc", "def", "cba", "fed" }
{ 24, 7, 63, 222, 190 }
Returns: 499

Problem url:

Problem stats url:




PabloGilberto , ivan_metelsky , nika

Problem categories:

Greedy, Simple Search, Iteration