codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

864B.md (1783B)


      1 Source: https://codeforces.com/problemset/problem/864/B
      2 
      3 B. Polycarp and Letters
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Polycarp loves lowercase letters and dislikes uppercase ones. Once he got a string *s* consisting only of lowercase and uppercase Latin letters.
     22 
     23 Let *A* be a set of positions in the string. Let's call it pretty if following conditions are met:
     24 
     25 * letters on positions from *A* in the string are all distinct and lowercase;
     26 * 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 *a*1 < *j* < *a*2 for some *a*1 and *a*2 from *A*).
     27 
     28 Write a program that will determine the maximum number of elements in a pretty set of positions.
     29 
     30 Input
     31 
     32 The first line contains a single integer *n* (1 ≤ *n* ≤ 200) — length of string *s*.
     33 
     34 The second line contains a string *s* consisting of lowercase and uppercase Latin letters.
     35 
     36 Output
     37 
     38 Print maximum number of elements in pretty set of positions for string *s*.
     39 
     40 Examples
     41 
     42 Input
     43 
     44 ```
     45 11  
     46 aaaaBaabAbA
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 2
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 12  
     59 zACaAbbaazzC
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 3
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 3  
     72 ABC
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 0
     79 ```
     80 
     81 Note
     82 
     83 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.
     84 
     85 In the second example desired positions can be 7, 8 and 11. There are other ways to choose pretty set consisting of three elements.
     86 
     87 In the third example the given string *s* does not contain any lowercase letters, so the answer is 0.