#3012. 「JOI 2019 Final」有趣的家庭菜园 3

内存限制:1024 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

译自 JOI 2019 Final T3「たのしいたのしいたのしい家庭菜園 / Growing Vegetable is Fun 3

家庭菜园专家 JOI 先生在他的家庭菜园中种植了一种叫 Joy 草的植物。在他的菜园里,有 N 个花盆自东向西摆放,编号分别为 1, \ldots, N 。每个花盆中有一株 Joy 草。

春天到了,JOI 先生注意到 Joy 草如他期望地长出了各种颜色的叶子,但他也发现 Joy 草的生长速度没有他期望的那么快。他查阅了书籍,找到了草的以下特点:

  • Joy 草有三种品种,分别会长出红色、绿色和黄色的叶子。

  • 如果两株同一颜色的 Joy 草紧密相邻,它们的生长速度就会减慢。

因此,JOI 先生决定重新摆放花盆,使得没有两株相邻的 Joy 草颜色相同。

花盆非常沉重,因此 JOI 先生每次只能交换相邻的两个花盆。形式化的说,JOI 先生每次操作可以选择一个 i (1 \le i < N) ,然后交换花盆 i 和花盆 i+1

请编写一个程序,计算最少的交换次数。

输入格式

从标准输入中读取数据。

第一行一个整数 N

接下来一行一个长度为 N 的字符串 S ,每个字符为 R,G,Y 中的一个,表示 Joy 草的颜色。

输出格式

输出数据到标准输出中。

输出一行一个整数,表示完成目标所需的最少操作次数。如果无解,输出 -1

样例

样例输入 1
5
RRGYY
样例输出 1
2
样例说明 1

一种合法的方案是:

  • 第一步:交换第三个花盆和第四个花盆。
  • 第二步:交换第二个花盆和第三个花盆。

在交换完成后,Joy 草的颜色序列为 RYRGY

可以证明 JOI 先生不能用少于 2 次交换完成目标,所以答案为 2

样例输入 2
6
RRRRRG
样例输出 2
-1
样例解释 2

在这个样例中,无论如何操作,都不能使任意两株相邻 Joy 草颜色不同。

样例输入 3
20
YYGYYYGGGGRGYYGRGRYG
样例输出 3
8

数据范围与提示

Subtask # 分值 N 特殊约定
1 5 N \le 15 -
2 55 N \le 60
3 15 - S 中的字符只有 R G
4 25 -

对于所有输入数据,有 1 \le N \le 400