/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
英小文字からなる長さ N の文字列 S が与えられます．
あなたは，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
Score : 300 points
Problem Statement
Given is a string S of length N consisting of lowercase English letters.
You can do the following operation on S any number of times.
- Choose its (non-empty) contiguous substring such that the first character and the last character are different, and delete this substring.
Determine whether it is possible to make S empty. If it is possible, find the minimum number of operations needed to do so.
Constraints
- 2 \leq N \leq 10^5
- S is a string of length N consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
N S
Output
If it is possible to make S empty, print the minimum number of operations needed to do so. Otherwise, print -1.
Sample Input 1
4 abba
Sample Output 1
2
We should do as follows: abba → (delete ab) → ba → (delete ba) → an empty string.
Sample Input 2
3 aba
Sample Output 2
-1