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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
If , we cannot perform any RSPs at all so the answer is just
.
Otherwise, the key observation is that groups of consecutive letters can all be merged into one letter, and we can treat 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 as a circle.
Time complexity:
Comments