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 翻译