B. Polycarp and Letters

time limit per test 

2 seconds

memory limit per test 

256 megabytes

input s

tandard input

output 

s

tandard output

 

Polycarp loves lowercase letters and dislikes uppercase ones. Once he got a string s consisting only of lowercase and uppercase Latin letters.

Let A be a set of positions in the string. Let's call it pretty if following conditions are met:

• letters on positions from A in the string are all distinct and lowercase;
• there are no uppercase letters in the string which are situated between positions from A (i.e. there is no such j that s[j] is an uppercase letter, and a1 < j < a2 for some a1 and a2 from A).

Write a program that will determine the maximum number of elements in a pretty set of positions.

Input

The first line contains a single integer n (1 ≤ n ≤ 200) — length of string s.

The second line contains a string s consisting of lowercase and uppercase Latin letters.

Output

Print maximum number of elements in pretty set of positions for string s.

Examples

input

11 aaaaBaabAbA

output

2

input

12 zACaAbbaazzC

output

3

input

3 ABC

output

0

Note

In the first example the desired positions might be 6 and 8 or 7 and 8. Positions 6 and 7 contain letters 'a', position 8 contains letter 'b'. The pair of positions 1 and 8 is not suitable because there is an uppercase letter 'B' between these position.

In the second example desired positions can be 7, 8 and 11. There are other ways to choose pretty set consisting of three elements.

In the third example the given string s does not contain any lowercase letters, so the answer is 0.

 

Analysis

该题题意非常之迷

首先给你个字符串，然后对该字符串进行信息统计

怎么个统计法呢

A 表示一个字符集

首先我们在他给的字符串（叫它 s 吧！）s里面随手画一个区间

这个区间需要满足：里面不包含大写字母

那么 A 保存的就是这个区间里含有的字母种类数（显然最多有26个元素）

最后输出 A 所包含字符集可能的最多数量

显然开个桶然后 O(n) 即可

 

Code

 

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5  6 bitset<100> buck; 7 char ctr; 8 int ans,n; 9 10 int main(){11     scanf("%d",&n);12     13     for(int i = 1;i <= n;i++){14         cin >> ctr;15         if(ctr <= 'Z' && ctr >= 'A'){16             ans = max(ans,(int)buck.count());17             buck.reset();18         }else{19             buck.set((int)(ctr-'a'));20         }21     }22     23     ans = max(ans,(int)buck.count());24     25     printf("%d",ans);26     27     return 0;28 }