← 返回题目列表

AtCoder · joi2020ho_b

B. JJOOII 2:第二部

中文机器翻译题面 查看原题

配点: 100 点

Bitaro 从他的朋友 Vivako 那里收到了一份生日礼物。 J,O,I 的 3 由类型字符组成的长度 N 字符串 我收到了 S 。 必须是大于或等于

K 在 1 的整数。K 字符 按此顺序排列的 J,K 字符 按此顺序排列的 O,K 字符 按此顺序排列的 I 字符串是等级 K 的 JOI 字符串 我们称之为。例如,JJOOII 是级别 这是 2 的 JOI 字符串。

Bitaro 已等级 我喜欢 K 的 JOI 字符串,所以以下 通过以任意顺序执行任意次数的 3 类型的操作,您可以创建一个字符串 S 级别 我决定将其转换为 K 的 JOI 字符串。 删除

  • 操作 1   文字列 S 的第一个字符。 删除
  • 操作 2   文字列 S 的最后一个字符。 删除既不是
  • 操作 3   文字列 S 开头也不是结尾的字符。

操作 3 很乏味,所以 3 执行尽可能少的次数来创建字符串 我想将其转换为 S 级别 我决定将其转换为 K 的 JOI 字符串。 大于或等于

长度为 N 字符串 我收到了 S 和 在 1 的整数 给定 K ,字符串 转换为 S 级别 我决定将其转换为 K 的 JOI 字符串所需的操作 编写一个程序,输出次数 3 的最小值。但是,无论您如何执行操作,字符串 如果无法转换为 S 级别 我决定将其转换为 K 的JOI字符串,则改为 输出 −1 。


入力

输入是按以下格式从标准输入给出的。N, K 是一个整数。S 是一个字符串。 最小次数

N K
S

出力

文字列 S 级别 我决定将其转换为 K 的 JOI 字符串所需的操作 编写一个程序,输出次数 3 是 输出为 1 行。但是,无论您如何执行操作,字符串 它是一个 S 级别 我决定将其转换为 K 的JOI字符串,则改为 输出 -1 。


制約

  • 3 \leqq N \leqq 200\,000.
  • 1 \leqq K \leqq \frac{N}{3}.
  • S 是 给出了 J,O,I 的 3 由类型字符组成的长度 N 字符串。

小課題

  1. (1 点) N \leqq 21.
  2. (12 点) N \leqq 3\,000.
  3. (87 点)没有额外的限制。

入力例 1

10 2
OJIJOIOIIJ

出力例 1

2

通过执行以下操作,字符串 可以将其转换为 S 级别 我决定将其转换为 K 的JOI字符串。

  1. 一、操作 执行 1 。字符串 它变成 S 是 给出了 JIJOIOIIJ 。
  2. 下一步操作 2 。字符串 它变成 S 是 给出了 JIJOIOII 。
  3. 下一步操作 3 并从头开始。 2 删除第一个字符。字符串 S 是 给出了 JJOIOII 。
  4. 上次操作 少于 3 并从头开始。 4 删除第一个字符。字符串 S 是 给出了 JJOOII 。

2 操作 无法用 3 进行转换,所以 输出2 。


入力例 2

9 3
JJJOOOIII

出力例 2

0

无需任何操作。


入力例 3

9 1
IIIOOOJJJ

出力例 3

-1

在这个输入示例中,无论你如何操作,字符串 无法转换为 S 级别 我决定将其转换为 1 的 JOI 字符串。