MakePalindrome | Topcoder Archive

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.

Definition

Class:: MakePalindrome
Method:: constructMinimal
Parameters:: String
Returns:: String[]
Method signature:: String[] constructMinimal(String card)
(be sure your method is public)

Constraints

card will contain between 1 and 1,000 characters, inclusive.
Each character in card will be a lowercase English letter ('a'-'z').

Examples

```
"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".
```
"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.
```
"aaabbbccc"
```
```
Returns: {"aba", "bcb", "cac" }
```
There are other solutions like {"aaa", "bbb", "ccc"}

"topcoder"

Returns: {"oco", "d", "e", "p", "r", "t" }

```
"z"
```
```
Returns: {"z" }
```

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.