#2161. 「POI2011 R2 Day1」Difference

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ceba_robot

题目描述

译自 POI 2011 Round 2. Day 1. A「Difference

给定一个长度为 n 的字符串 s ,取它的一个子串 t ,使得出现次数最多的字母与出现次数最少的字母的出现次数相差最大。请求出这个最大值。

说明:

  • 出现次数最少的字母至少要出现一次。换句话说,未出现的字母不被统计。
  • 当子串只由一种字母构成时,出现次数最多的字母与出现次数最少的字母是一样的。

输入格式

第一行,一个整数 n
第二行,字符串 s

输出格式

一行,一个整数,表示答案。

样例

样例输入

10
aabbaaabab

样例输出

3

样例说明

子串 aaabaa 出现 4 次,b 出现 1 次,相差 3 次,即为答案。

数据范围与提示

Task author: Jacek Tomasiewicz.

数据范围

对于 30\% 的数据, n \le 100
对于 100\% 的数据, 1 \le n \le 10^6 ,保证字符串中只含有小写英文字母。