## Editorial for Mock CCC '21 S2 - Colorful Strings

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.**Each letter is independent. Let be the number of times character appears. The answer is therefore .

## Comments

Can someone explain the reasoning behind why this is the answer? I'm too small brain to understand.

For each unique character 'x', it will appear in f(x) different positions in the original string. There are two possibilities, the character 'x' appears in the subsequence or it doesn't appear at all. If the character 'x' appears in the subsequence, there are f(x) many ways to choose 1 of these positions. Otherwise, there is only one way the character 'x' doesn't appear at all (we don't select any of these positions). Hence, we repeatedly multiply the expression f(x)+1 for each unique character that appears in the original string.