题目描述

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

你可以对 $S$ 进行如下操作任意次：

• 选择一个首尾字符不同的连续（非空）子串，并将其删除。

请判断是否可以将 $S$ 变为空字符串。如果可以，请输出所需的最小操作次数；如果不可以，输出 $-1$。

输入格式

输入以以下格式从标准输入读入：

$N$ $S$

输出格式

如果可以将 $S$ 变为空字符串，输出所需的最小操作次数。如果不可以，输出 $-1$。

样例 1

输入

4
abba

输出

2

样例 2

输入

3
aba

输出

-1

说明/提示

限制

• $2 \leq N \leq 10^5$
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串。

样例解释 1

abba →（选择并删除 ab）→ ba →（选择并删除 ba）→ 空字符串。

由 ChatGPT 4.1 翻译