Letter Frequency Difference

Time limit1sMemory limit128 MB

Summary

Pick any contiguous fragment of a lowercase word to maximize the gap between its most and least frequent letters.

Level: Medium7 of 10
Topics: Dynamic programming, Prefix sum, Greedy
Solved: No attempts yet

Problem

You are given a word of length $n$ consisting only of lower-case letters of the English alphabet ('a' to 'z'). Choose one non-empty contiguous fragment (a single, unbroken piece) of the word so as to maximize the difference between the number of occurrences of the most frequent letter and the number of occurrences of the least frequent letter within that fragment. The least frequent letter must occur at least once in the fragment. In particular, if the fragment consists of a single distinct letter, then the most and least frequent letters coincide and the difference is $0$ .

Input

The first line contains an integer $n$ ( $1 \le n \le 10^6$ ), the length of the word. The second line contains the word: a string of $n$ lower-case English letters.

Output

Print a single integer: the maximum possible difference between the number of occurrences of the most frequent letter and the number of occurrences of the least frequent letter, taken over every non-empty contiguous fragment of the word.

Hint

For example, when the word is aabbaaabab, the fragment aaaba contains a four times and b once, giving a difference of $3$ , which is the maximum.

Examples3

Example 1
Input
```
10
aabbaaabab
```
Expected output
```
3
```
Example 2
Input
```
1
a
```
Expected output
```
0
```
Example 3
Input
```
4
aaab
```
Expected output
```
2
```