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 $f(x)$ ~f(x)~ be the number of times character $x$ ~x~ appears. The answer is therefore:

$\displaystyle \prod_x (f(x)+1)$ $$\displaystyle \prod_x (f(x)+1)$$

Comments

8

JohnstonLiu commented on Feb. 9, 2021, 6:22 p.m.

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

7

fliptheswitch commented on Feb. 9, 2021, 6:43 p.m.

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.