35141번 - Palindrome Partition 스페셜 저지다국어

A palindrome is a string that reads the same forwards as backwards. For example, radar, noon, and a are palindromes, while bathtub, thought, and is are not.

Given a string $S$ consisting only of lowercase English letters. You can rearrange the letters in $S$ in any order you like. Your task is to split $S$ after rearrangement into as few palindromic substrings as possible.

The first and only line contains the string $S$ ($1 \le |S| \le 200000$) containing lowercase English letters.

On the first line, print the minimum number $k$ of palindrome substrings.

On the next $k$ lines, print the palindromes that the string $S$ (after rearrangement) can be split into. If there are multiple ways to split, you may output any of them.

Explanation of Sample 1: We can rearrange the input string into levelracecar, then split the string into two palindromes: level and racecar. No rearrangement can produce a single palindrome, so the minimum number of palindromes is $2$.