Palindrome Partition Codechef Solution

Problem

JJ has a binary string $S$ of length $2\cdot N$. He wants to partition it into $M$ substrings such that:

• $1\le M\le 2\cdot N$
• Each S_iSi​ belongs to exactly one partition
• None of the partitioned substrings is a palindrome

For example: One of the valid partitions of $10010011$ is \underline{100}\ \underline{10}\ \underline{011}100​ 10​ 011​.

Can you find any partition satisfying the above conditions? If no such partition exists, output $-1$.

A string is called palindrome if it reads the same backwards and forwards, for e.g. $1001$ and $00100$ are palindromic strings.

Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — half the length of the binary string $S$.
• The second line of each test case contains a binary string $S$ of length $2\cdot N$ containing $0$s and $1$s only.

Output Format

For each test case,

• In the first line, output: $M$ $(1\le M\le 2\cdot N)$ – the number of partitions
• In the second line, output $M$ integers: L_1, L_2, \dots, L_ML1​,L2​,…,LM​ – where L_iLi​ denotes the length of the i^{th}ith partitioned substring. (Note that L_1 + L_2 + \dots + L_M = 2 \cdot NL1​+L2​+⋯+LM​=2⋅N and L_i \ge 1Li​≥1 for all $i$)

Constraints

Sample 1:

3
4
10010011
1
00
3
101101

3
3 2 3
-1
2
2 4

Explanation:

Test Case 1: Explained in the problem statement.

Test Case 2: It can be proven that no valid partition of $00$ exists.

Test Case 3: One of the valid partitions of $101101$ is \underline{10}\ \underline{1101}10​ 1101​.