Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の英小文字のみからなる文字列 s が与えられます。
すぬけ君は s から fox
という部分文字列を 1 つ選んで取り除き、その前後の部分を連結する、という操作を何度でも行うことができます。
すぬけ君が操作を何度か行ったあと、s の長さは最小でいくつになりえますか?
制約
- 1 \leq N \leq 2 \times 10^{5}
- s は英小文字のみからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N s
出力
すぬけ君が操作を何度か行ったあとの s の長さとしてありうる値の最小値を出力せよ。
入力例 1
6 icefox
出力例 1
3
icefox
の末尾fox
を取り除くことで s をice
にすることができます。
入力例 2
7 firebox
出力例 2
7
fox
という部分文字列が存在しません。
入力例 3
48 ffoxoxuvgjyzmehmopfohrupffoxoxfofofoxffoxoxejffo
出力例 3
27
Score : 400 points
Problem Statement
Given is a string S of length N consisting of lowercase English letters.
Snuke can do this operation any number of times: remove fox
occurring as a substring from s and concatenate the remaining parts of s.
What is the minimum possible length of s after some number of operations by Snuke?
Constraints
- 1 \leq N \leq 2 \times 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
Print the minimum possible length of s after some number of operations by Snuke.
Sample Input 1
6 icefox
Sample Output 1
3
- By removing the
fox
at the end oficefox
, we can turn s intoice
.
Sample Input 2
7 firebox
Sample Output 2
7
fox
does not occur as a substring.
Sample Input 3
48 ffoxoxuvgjyzmehmopfohrupffoxoxfofofoxffoxoxejffo
Sample Output 3
27