完美字串


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

字串題是資訊競賽中較為困難的題目,只要出現在比賽中經常造成滅台的慘案,因此也出現不少題目披著字串的外衣,實際上要用其他演算法解決,而選手們在比賽中往往難以識破,使得這些題目達到以假亂真的效果,最近一次發生這件事情要追溯到2024YTP高中組的決賽p9,全場沒有隊伍提交。現在,有一道看起來像字串的字串題,請你用學過的字串演算法解決這道題吧!

定義一個字串是"完美"的當此字串的每個字元都相同,給定一個長度為 \(n\) 的字串,此字串由小寫字母組成,請你輸出最長完美子字串的長度。

正式的說,給定一個字串 \(s_1s_2...s_n\) ,找出一組 \((l,r)\) 使得 \(l \leq r\) , \(s_l=s_{l+1}=...=s_r\) ,且 \(r-l+1\) 最大,輸出 \((r-l+1)\) 即可

Input

第一行輸入一個正整數 \(n(1 \leq n \leq 10^5)\)

第二行輸入一個長度為 \(n\) 的字串 \(S\) ,保證 \(S\) 的每個字元均為小寫字母

Output

輸出一個正整數,代表給定字串中最長完美子字串的長度

Constraints

第 \(1\) 組測資, \(n \leq 500\) 。 (\(2 \%\))

第 \(2\) 組測資, \(n \leq 5000\) 。 (\(8 \%\))

第 \(3\) 組測資,無特別限制。 (\(90 \%\))

Sample Input 1
10
ballooncup
Sample Output 1
2
Sample Input 2
18
goodluckandhavefun
Sample Output 2
2

Comments

There are no comments at the moment.