241996 - 展柜编号整理

题目描述

校园博物馆把一排展柜从左到右编好位置,每个展柜上贴着一个大写英文字母,表示展品类别。

工作人员要给展柜制作说明牌。同一块说明牌只能负责一段位置连续、类别相同的展柜。每个展柜恰好由一块说明牌负责;中间隔着其他类别时,即使字母相同,也不能共用说明牌。

工作人员希望使用的说明牌总数最少。请输出最少需要多少块说明牌,以及一块说明牌最多可以负责多少个展柜。

输入

第一行一个整数 n,表示展柜数量。

第二行一个长度为n的字符串,只含大写英文字母。第i个字符表示从左到右第i个展柜的类别。

【数据范围】

对全部数据,1 \le n \le 10000。字符串长度恰好为n,字符均为A至Z。

输出

输出两个整数,用一个空格隔开,依次表示最少的说明牌数量,以及使用最少数量说明牌时,一块说明牌负责的最多展柜数。

样例

输入

10
AAABBCCCCA

输出

4 4

输入

5
ZZZZZ

输出

1 5
说明

【样例解释1】

分成AAA、BB、CCCC、A四段。最少需要4块说明牌,其中负责CCCC的说明牌覆盖4个展柜。开头和结尾的A不能合在一起。

【样例解释2】

所有展柜连续且类别相同,一块说明牌即可负责全部5个展柜。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 17
通过人数 8
金币数量 2 枚
难度 入门


上一题 下一题