Editorial for Singularity Cup P2 - Reverse Substring Partitioning - Olympiads Online Judge

Editorial for Singularity Cup P2 - Reverse Substring Partitioning

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Mystical

If $S_1 \ne S_N$ $S_{1} \neq S_{N}$ , we cannot perform any RSPs at all so the answer is just $N$ $N$ .

Otherwise, the key observation is that groups of consecutive letters can all be merged into one letter, and we can treat $S$ $S$ as circular because the letters at the very start of the string will end up being adjacent to the letters at the very end of the string once an RSP is performed.

Thus, the problem reduces to counting the number of groups of consecutive letters while treating $S$ $S$ as a circle.

Time complexity: $\mathcal{O}(N)$ $O (N)$

Comments

There are no comments at the moment.