← 返回题目列表

AtCoder · agc054_a

A. 删除子字符串

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

分数: 300 点

问题陈述

给定的是一个字符串 S 长度 N 由小写英文字母组成。

您可以对 S 任意次数。

  • 选择其(非空)连续子字符串,使第一个字符和最后一个字符不同,然后删除该子字符串。

判断是否可以使 S 空。如果可能的话,找出执行此操作所需的最少操作数。

约束

  • 2 \leq N \leq 10^5
  • S 是一个长度为 N 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

N
S

输出

如果可以的话 S 空,打印执行此操作所需的最少操作数。 否则,打印 -1.


示例输入 1

4
abba

示例输出 1

2

我们应该这样做: abba →(删除 ab) → ba →(删除 ba) → 空字符串。


示例输入 2

3
aba

示例输出 2

-1