完美字串
字串題是資訊競賽中較為困難的題目,只要出現在比賽中經常造成滅台的慘案,因此也出現不少題目披著字串的外衣,實際上要用其他演算法解決,而選手們在比賽中往往難以識破,使得這些題目達到以假亂真的效果,最近一次發生這件事情要追溯到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