Interesting Swap

**Please note that this problem has subtasks**. You are given a string $S$ of length $N$. In one operation, you can select a **non-empty** *prefix* and a **non-empty** *suffix* which do **not intersect**; and swap them. For example let $S =$ `avfdgs`. In one operation, you can choose *prefix* of length $2$ and *suffix* of length $3$, and swap them to make $S =$ `dgsfav`. Your task it to **sor