H. Palindromic Cut

Codeforces

IDCF883H

Time3000ms

Memory256MB

Difficulty—

brute forceimplementationstrings

English · Original

Chinese · Translation

Formal · Original

Kolya has a string _s_ of length _n_ consisting of lowercase and uppercase Latin letters and digits. He wants to rearrange the symbols in _s_ and cut it into the minimum number of parts so that each part is a palindrome and all parts have _the same lengths_. A palindrome is a string which reads the same backward as forward, such as _madam_ or _racecar_. Your task is to help Kolya and determine the minimum number of palindromes of equal lengths to cut _s_ into, if it is allowed to rearrange letters in _s_ before cuttings. ## Input The first line contains an integer _n_ (1 ≤ _n_ ≤ 4·105) — the length of string _s_. The second line contains a string _s_ of length _n_ consisting of lowercase and uppercase Latin letters and digits. ## Output Print to the first line an integer _k_ — minimum number of palindromes into which you can cut a given string. Print to the second line _k_ strings — the palindromes themselves. Separate them by a space. You are allowed to print palindromes in arbitrary order. All of them should have the same length. [samples]

[{"iden":"statement","content":"Kolya 有一个长度为 $n$ 的字符串 $s$，由小写和大写拉丁字母及数字组成。\n\n他希望重新排列 $s$ 中的字符，并将其切割成最少数量的子串，使得每个子串都是回文，且所有子串的长度 _相同_。回文是指正读和反读都相同的字符串，例如 _madam_ 或 _racecar_。\n\n你的任务是帮助 Kolya，确定在允许重新排列 $s$ 中的字母后，最少能将该字符串切割成多少个长度相等的回文串。\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 4·10^5$) —— 字符串 $s$ 的长度。\n\n第二行包含一个长度为 $n$ 的字符串 $s$，由小写和大写拉丁字母及数字组成。\n\n请在第一行输出一个整数 $k$ —— 你能将给定字符串切割成的最少回文串数量。\n\n请在第二行输出 $k$ 个字符串 —— 这些回文串本身。用空格分隔。你可以按任意顺序输出回文串，但它们都必须具有相同的长度。"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 ≤ n ≤ 4·10^5$) —— 字符串 $s$ 的长度。第二行包含一个长度为 $n$ 的字符串 $s$，由小写和大写拉丁字母及数字组成。"},{"iden":"output","content":"请在第一行输出一个整数 $k$ —— 你能将给定字符串切割成的最少回文串数量。请在第二行输出 $k$ 个字符串 —— 这些回文串本身。用空格分隔。你可以按任意顺序输出回文串，但它们都必须具有相同的长度。"},{"iden":"examples","content":"输入6aabaac输出2aba aca 输入80rTrT022输出102TrrT20 输入2aA输出2a A "}] 请注意：原始输入中 "Input80rTrT022" 和 "Output102TrrT20" 等部分存在格式问题（缺少换行），但在题面中应视为独立的测试用例。翻译已忠实保留原始格式，仅翻译自然语言部分，数学公式和下划线强调均未改动。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the string $ s $. Let $ \mathcal{C} $ be the multiset of character frequencies in $ s $, i.e., $ \mathcal{C} = \{ (c, f_c) \mid c \in \text{alphabet}, f_c = \text{count of } c \text{ in } s \} $. **Constraints** 1. $ 1 \leq n \leq 4 \cdot 10^5 $ 2. Each character in $ s $ is a lowercase/uppercase Latin letter or digit. **Objective** Find the minimum integer $ k \geq 1 $ such that $ s $ can be rearranged and partitioned into $ k $ palindromic substrings of equal length $ \ell = n/k $, where: - Each palindrome has length $ \ell $, - $ k \mid n $, - The multiset $ \mathcal{C} $ admits a decomposition into $ k $ palindromes of length $ \ell $. A string of length $ \ell $ is a palindrome if at most one character has an odd frequency within it. Thus, for the entire multiset $ \mathcal{C} $, the total number of characters with odd frequency, denoted $ o $, must satisfy $ o \leq k $, since each palindrome can accommodate at most one odd-frequency character. **Minimization Goal** Minimize $ k $ such that: - $ k \mid n $, - $ k \geq o $, - $ \ell = n/k $ is an integer. **Output** - First line: $ k $ - Second line: $ k $ palindromes of length $ \ell = n/k $, formed by rearranging $ s $, each being a palindrome.

Samples

Input #1

6
aabaac

Output #1

2
aba aca

Input #2

8
0rTrT022

Output #2

1
02TrrT20

Input #3

2
aA

Output #3

2
a A

API Response (JSON)

{
  "problem": {
    "name": "H. Palindromic Cut",
    "description": {
      "content": "Kolya has a string _s_ of length _n_ consisting of lowercase and uppercase Latin letters and digits. He wants to rearrange the symbols in _s_ and cut it into the minimum number of parts so that each ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF883H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Kolya has a string _s_ of length _n_ consisting of lowercase and uppercase Latin letters and digits.\n\nHe wants to rearrange the symbols in _s_ and cut it into the minimum number of parts so that each ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"Kolya 有一个长度为 $n$ 的字符串 $s$，由小写和大写拉丁字母及数字组成。\\n\\n他希望重新排列 $s$ 中的字符，并将其切割成最少数量的子串，使得每个子串都是回文，且所有子串的长度 _相同_。回文是指正读和反读都相同的字符串，例如 _madam_ 或 _racecar_。\\n\\n你的任务是帮助 Kolya，确定在允许重新排...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the string $ s $.  \nLet $ \\mathcal{C} $ be the multiset of character frequencies in $ s $, i.e., $ \\mathcal{C} = \\{ (c, f_c) \\mid c \\in \\t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments