B. Polycarp and Letters

Codeforces

IDCF864B

Time2000ms

Memory256MB

Difficulty—

brute forceimplementationstrings

English · Original

Chinese · Translation

Formal · Original

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 _a_1 < _j_ < _a_2 for some _a_1 and _a_2 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_. [samples] ## 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.

Polycarp 喜欢小写字母，不喜欢大写字母。有一天他得到了一个字符串 #cf_span[s]，该字符串仅由小写和大写拉丁字母组成。设 #cf_span[A] 为字符串中的位置集合。如果满足以下条件，则称其为 _pretty_：请编写一个程序，确定 _pretty_ 位置集合的最大元素个数。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200]) —— 字符串 #cf_span[s] 的长度。第二行包含一个由小写和大写拉丁字母组成的字符串 #cf_span[s]。请输出字符串 #cf_span[s] 的 _pretty_ 位置集合的最大元素个数。在第一个例子中，所需的位罝可能是 #cf_span[6] 和 #cf_span[8]，或 #cf_span[7] 和 #cf_span[8]。位置 #cf_span[6] 和 #cf_span[7] 包含字母 '_a_'，位置 #cf_span[8] 包含字母 '_b_'。位置对 #cf_span[1] 和 #cf_span[8] 不合适，因为这两个位置之间有一个大写字母 '_B_'。在第二个例子中，所需的位罝可以是 #cf_span[7]、#cf_span[8] 和 #cf_span[11]。还有其他方式可以选择包含三个元素的 _pretty_ 集合。在第三个例子中，给定的字符串 #cf_span[s] 不包含任何小写字母，因此答案为 #cf_span[0]。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200]) —— 字符串 #cf_span[s] 的长度。第二行包含一个由小写和大写拉丁字母组成的字符串 #cf_span[s]。 ## Output 请输出字符串 #cf_span[s] 的 _pretty_ 位置集合的最大元素个数。 [samples] ## Note 在第一个例子中，所需的位罝可能是 #cf_span[6] 和 #cf_span[8]，或 #cf_span[7] 和 #cf_span[8]。位置 #cf_span[6] 和 #cf_span[7] 包含字母 '_a_'，位置 #cf_span[8] 包含字母 '_b_'。位置对 #cf_span[1] 和 #cf_span[8] 不合适，因为这两个位置之间有一个大写字母 '_B_'。在第二个例子中，所需的位罝可以是 #cf_span[7]、#cf_span[8] 和 #cf_span[11]。还有其他方式可以选择包含三个元素的 _pretty_ 集合。在第三个例子中，给定的字符串 #cf_span[s] 不包含任何小写字母，因此答案为 #cf_span[0]。

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the string $ s \in \Sigma^n $, where $ \Sigma = \{ \text{a}, \dots, \text{z}, \text{A}, \dots, \text{Z} \} $. Let $ P \subseteq \{1, 2, \dots, n\} $ be a set of positions. **Constraints** A set $ P $ is *pretty* if and only if: 1. For every position $ i \in P $, the character $ s[i] $ is a *lowercase* letter. 2. For every pair of positions $ i, j \in P $ with $ i < j $, all characters $ s[k] $ for $ k \in \{i+1, \dots, j-1\} $ are *lowercase*. **Objective** Find the maximum cardinality of a pretty set $ P $.

Samples

Input #1

11
aaaaBaabAbA

Output #1

Input #2

12
zACaAbbaazzC

Output #2

Input #3

3
ABC

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Polycarp and Letters",
    "description": {
      "content": "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 cal",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF864B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp loves lowercase letters and dislikes uppercase ones. Once he got a string _s_ consisting only of lowercase and uppercase Latin letters.\n\nLet _A_ be a set of positions in the string. Let's cal...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 喜欢小写字母，不喜欢大写字母。有一天他得到了一个字符串 #cf_span[s]，该字符串仅由小写和大写拉丁字母组成。\n\n设 #cf_span[A] 为字符串中的位置集合。如果满足以下条件，则称其为 _pretty_：\n\n请编写一个程序，确定 _pretty_ 位置集合的最大元素个数。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200]) —...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the string $ s \\in \\Sigma^n $, where $ \\Sigma = \\{ \\text{a}, \\dots, \\text{z}, \\text{A}, \\dots, \\text{Z} \\} $.  \nLet $ P \\subseteq \\{1, 2, \\d...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments