Consider this problem — 766C - Махмуд и сообщение. It asks the number of ways to partition the given string such that each substring holds the given condition. I understood how to solve this.

At first, I interpreted the problem slightly differently. I thought you have to count the unique combination of the partition of the string. But I couldn't come up with the solution for this. How to not overcount/find unique combinations?

For example,

Assume that the following two partitions are valid,

String — "abbba"

1. a|bb|b|a

2. a|b|bb|a

They should be considered the same in this variation of the problem.

How to approach this?