PalindromeGame
SRM 499 · 2010-11-01 · by lyrically
SRM 499 · 2010-11-01 · by lyrically · Greedy, Simple Search, Iteration
Problem Statement
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 aString[] 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.
You are given a
Constraints
- 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.
Examples
0)
{ "topcoder", "redcoder", "redocpot" }
{ 7, 5, 3 }
Returns: 10
You can choose "topcoder" with 7 and "redocpot" with 3 to get a palindrome "topcoderredocpot".
1)
{ "rabbit" }
{ 1000000 }
Returns: 0
No palindrome can be made.
2)
{ "abc", "abc", "def", "cba", "fed" }
{ 24, 7, 63, 222, 190 }
Returns: 499
3)
{ "abc", "cba", "def", "abc", "fed" }
{ 24, 7, 63, 222, 190 }
Returns: 482
4)
{ "a" }
{ 1 }
Returns: 1
Submissions are judged against all 204 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PalindromeGame with a public method int getMaximum(vector<string> front, vector<int> back) · 204 test cases · 2 s / 256 MB per case