校园博物馆把一排展柜从左到右编好位置,每个展柜上贴着一个大写英文字母,表示展品类别。
工作人员要给展柜制作说明牌。同一块说明牌只能负责一段位置连续、类别相同的展柜。每个展柜恰好由一块说明牌负责;中间隔着其他类别时,即使字母相同,也不能共用说明牌。
工作人员希望使用的说明牌总数最少。请输出最少需要多少块说明牌,以及一块说明牌最多可以负责多少个展柜。
第一行一个整数 n,表示展柜数量。
第二行一个长度为n的字符串,只含大写英文字母。第i个字符表示从左到右第i个展柜的类别。
对全部数据,1 \le n \le 10000。字符串长度恰好为n,字符均为A至Z。
输出两个整数,用一个空格隔开,依次表示最少的说明牌数量,以及使用最少数量说明牌时,一块说明牌负责的最多展柜数。
10 AAABBCCCCA
4 4
5 ZZZZZ
1 5
分成AAA、BB、CCCC、A四段。最少需要4块说明牌,其中负责CCCC的说明牌覆盖4个展柜。开头和结尾的A不能合在一起。
所有展柜连续且类别相同,一块说明牌即可负责全部5个展柜。