409668: GYM103677 F Sour Grapes

Tweedledee and Tweedledum look similar, but their preferences are anything but. In particular, Tweedledee loves raisins but dislikes currants, while Tweedledum loves currants but dislikes raisins. However, both Tweedledee and Tweedledum hate sultanas. We can model this in the following way:

When Tweedledee eats a raisin, his happiness increases by 1; when he eats a currant, his happiness decreases by 1; when he eats a sultana, his happiness decreases by 2. On the other hand, Tweedledum's happiness increases by 1 when he eats a currant, decreases by 1 when he eats a raisin, and decreases by 2 when he eats a sultana.

Tweedledee and Tweedledum are attending a feast hosted by the March Hare and the Hatter. On the table lies a row of raisins, currants, and sultanas. Tweedledee sits on the left side, while Tweedledum sits on the right side. When the feast commences, they begin eating the fruits one-by-one, starting from their side.

Tweedledee and Tweedledum both start with happiness 0. In order to display proper manners they may only eat in the manner described above (no sharing, eating out-of-order, etc.) They may eat any number of fruits (so long as the combined number of fruits eaten does not exceed the total number on the table). What is the maximum total happiness (happiness of Tweedledee + happiness of Tweedledum) that can be attained?

The first line contains an integer $$$N$$$, denoting the total number of raisins, currants, and sultanas. ($$$1 \le N \le 10^6$$$)

The second line contains a string $$$S$$$ of length $$$N$$$ composed of the characters $$$R$$$, $$$C$$$, and $$$S$$$, denoting raisins, currants, and sultanas, respectively.

Output one integer, the maximum total happiness that can be attained, defined as the happiness of Tweedledee plus the happiness of Tweedledum.

12
RRCRRRSCSCCC

7

In the first example, the optimal solution is when Tweedledee eats the fruits at positions 1-6, and Tweedledum eats the fruits at positions 10-12. Then Tweedledee eats 5 raisins and 1 currant, so he has a happiness of 4; Tweedledum eats 3 currants, so he has a happiness of 3. The total happiness, then, is 4+3=7.