#2161. 「POI2011 R2 Day1」Difference

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

题目描述

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

A word consisting of n lower-case letters of the English alphabet ('a'-'z') is given. We would like to choose a non-empty contiguous (i.e. one-piece) fragment of the word so as to maximise the difference in the number of occurrences of the most and the least frequent letter in the fragment. We are assuming that the least frequent letter has to occur at least once in the resulting fragment. In particular, should the fragment contain occurrences of only one letter, then the most and the least frequent letter in it coincide.

输入格式

The first line of the standard input holds one integer n ( 1 \le n \le 1000000 ) that denotes the length of the word. The second line holds a word consisting of n lower-case letters of the English alphabet.

In tests worth at least 30\% of the points it additionally holds that n \le 100 .

输出格式

The first and only line of the standard output is to hold a single integer, equal to the maximum difference in the number of occurrences of the most and the least frequent letter that is attained in some non-empty contiguous fragment of the input word.

样例

For the input data:

10
aabbaaabab

the correct result is:

3

Explanation of the example: The fragment that attains the difference of 3 in the number of occurrences of a and b is aaaba.

数据范围与提示

Task author: Jacek Tomasiewicz.