Connection Status:
Competition Arena > MakePalindrome

MakePalindrome

SRM 712 · 2017-02-20 · by cgy4ever

SRM 712 · 2017-02-20 · by cgy4ever · Math
Class Name: MakePalindrome
Return Type: String[]
Method Name: constructMinimal
Arg Types: (string)
Problem Statement

Problem Statement

You have some cards. Each card contains a single lowercase letter. You are given these letters as the characters of the String card.

A palindrome is a string that reads the same forwards and backwards. Examples of palindromes: "eve", "abba", "aaaaaa", and "racecar".

Use the cards you have to spell some palindromes. In particular:
  • Each card must be used in exactly one of the palindromes.
  • The total number of palindromes must be as small as possible.
Return a String[] containing the palindromes you built. (Each element of the return value should be one of the palindromes.)

A solution always exists. If there are multiple optimal solutions, you may choose and output any one of them.

Constraints

  • card will contain between 1 and 1,000 characters, inclusive.
  • Each character in card will be a lowercase English letter ('a'-'z').
Examples
0)
"abbaa"
Returns: {"ababa" }

We can rearrange all letters into a single palindrome. There are two ways to do so: one is "ababa", the other is "baaab".

1)
"abc"
Returns: {"a", "b", "c" }

This time the only solution is to build three palindromes, each consisting of a single letter. Note that you may return the three strings in any order.

2)
"aaabbbccc"
Returns: {"aba", "bcb", "cac" }

There are other solutions like {"aaa", "bbb", "ccc"}

3)
"topcoder"
Returns: {"oco", "d", "e", "p", "r", "t" }
4)
"z"
Returns: {"z" }

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

Coding Area

Language: C++17 · define a public class MakePalindrome with a public method vector<string> constructMinimal(string card) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous