AT_arc014_3 [ARC014C] 魂の還る場所

高桥君非常喜欢用塑料制成的圆筒和神奇的红、蓝、绿三色小球。 这些小球的大小刚好可以放进圆筒中。 我们把圆筒的两端分别称为右端和左端，可以从任意一端将小球放入圆筒。 这些小球有一个特性：当相同颜色的小球相邻接触时，它们会消失。 另外，给定这三种颜色小球的放入顺序，只能改变每个小球从左端还是右端放入，放完所有小球后，圆筒中剩余的小球数量会有所不同。 现在给定这三种颜色小球的放入顺序，请你计划如何选择每个小球的放入端，使得最后圆筒中剩下的小球数量最少，并输出这个最小值。 输入格式如下。

第 $1$ 行输入一个整数 $N$，表示小球的数量，满足 $1 \leq N \leq 50$。 第 $2$ 行输入一个长度为 $N$ 的字符串 $S$，表示小球的放入顺序。$S$ 仅由 $R$、$G$、$B$ 三种字符组成，分别表示红、绿、蓝三种颜色的小球。

输出一个整数，表示经过最优放置后，圆筒中剩余小球的最小数量。 输出末尾需换行。

- 若仅能解决 $1 \leq N \leq 15$ 的情况，可获得 $30$ 分的部分分数。 ## 样例 ``` 9 RGBGGBGBR ``` ``` 1 ``` - 首先放入 $R$，圆筒为 $R$。 - 接着将 $G$ 从左端放入，圆筒为 $GR$。 - 将 $B$ 从右端放入，圆筒为 $GRB$。 - 将 $G$ 从右端放入，圆筒为 $GRBG$。 - 再将 $G$ 从右端放入，圆筒为 $GRBGG$。 - 此时两个 $G$ 相邻，消失，圆筒变为 $GRB$。 - 将 $B$ 从右端放入，圆筒为 $GRBB$。 - 两个 $B$ 相邻，消失，圆筒变为 $GR$。 - 将 $G$ 从左端放入，圆筒为 $GGR$。 - 两个 $G$ 相邻，消失，圆筒变为 $R$。 - 将 $B$ 从左端放入，圆筒为 $BR$。 - 将 $R$ 从右端放入，圆筒为 $BRR$。 - 两个 $R$ 相邻，消失，圆筒变为 $B$。 - 因此最终只剩下 $1$ 个 $B$，答案为 $1$。 ``` 6 RGBRGB ``` ``` 0 ``` 由 ChatGPT 4.1 翻译