[Solution] 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_i$ 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}$.

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

• In the second line, output $M$ integers: $L_1, L_2, \dots, L_M$ - where $L_i$ denotes the length of the $i^{th}$ partitioned substring. (Note that $L_1 + L_2 + \dots + L_M = 2 \cdot N$ and $L_i \ge 1$ for all $i$)

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}$.