B. File Name

Codeforces

IDCF978B

Time1000ms

Memory256MB

Difficulty—

greedystrings

English · Original

Chinese · Translation

Formal · Original

You can not just take the file and send it. When Polycarp trying to send a file in the social network "Codehorses", he encountered an unexpected problem. If the name of the file contains three or more "_x_" (lowercase Latin letters "_x_") in a row, the system considers that the file content does not correspond to the social network topic. In this case, the file is not sent and an error message is displayed. Determine the minimum number of characters to remove from the file name so after that the name does not contain "_xxx_" as a substring. Print _0_ if the file name does not initially contain a forbidden substring "_xxx_". You can delete characters in arbitrary positions (not necessarily consecutive). If you delete a character, then the length of a string is reduced by $1$. For example, if you delete the character in the position $2$ from the string "_exxxii_", then the resulting string is "_exxii_". ## Input The first line contains integer $n$ $(3 \le n \le 100)$ — the length of the file name. The second line contains a string of length $n$ consisting of lowercase Latin letters only — the file name. ## Output Print the minimum number of characters to remove from the file name so after that the name does not contain "_xxx_" as a substring. If initially the file name dost not contain a forbidden substring "_xxx_", print _0_. [samples] ## Note In the first example Polycarp tried to send a file with name contains number $33$, written in Roman numerals. But he can not just send the file, because it name contains three letters "_x_" in a row. To send the file he needs to remove any one of this letters.

你不能直接取文件并发送。当 Polycarp 尝试在社交网络 "Codehorses" 中发送文件时，遇到了一个意外的问题。如果文件名中包含三个或更多连续的 "_x_"（小写拉丁字母 "_x_"），系统会认为文件内容与社交网络主题不符。此时，文件将不被发送，并显示错误信息。请确定最少需要从文件名中删除多少个字符，使得删除后文件名中不再包含 "_xxx_" 作为子串。如果文件名初始时就不包含禁止子串 "_xxx_"，请输出 _0_。你可以删除任意位置的字符（不一定连续）。删除一个字符后，字符串长度减少 $1$。例如，如果从字符串 "_exxxii_" 中删除位置 $2$ 的字符，则结果字符串为 "_exxii_"。第一行包含整数 $n$ $(3 lt.eq n lt.eq 100)$ —— 文件名的长度。第二行包含一个长度为 $n$ 的字符串，仅由小写拉丁字母组成 —— 文件名。请输出最少需要删除的字符数量，使得删除后文件名中不再包含 "_xxx_" 作为子串。如果初始时文件名就不包含禁止子串 "_xxx_"，请输出 _0_。在第一个例子中，Polycarp 尝试发送一个文件名包含罗马数字 $33$ 的文件。但他不能直接发送该文件，因为文件名中包含三个连续的 "_x_" 字母。为了发送文件，他需要删除其中任意一个字母。 ## Input 第一行包含整数 $n$ $(3 lt.eq n lt.eq 100)$ —— 文件名的长度。第二行包含一个长度为 $n$ 的字符串，仅由小写拉丁字母组成 —— 文件名。 ## Output 请输出最少需要删除的字符数量，使得删除后文件名中不再包含 "_xxx_" 作为子串。如果初始时文件名就不包含禁止子串 "_xxx_"，请输出 _0_。 [samples] ## Note 在第一个例子中，Polycarp 尝试发送一个文件名包含罗马数字 $33$ 的文件。但他不能直接发送该文件，因为文件名中包含三个连续的 "_x_" 字母。为了发送文件，他需要删除其中任意一个字母。

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the string. Let $ s = s_1 s_2 \dots s_n $ be a string of length $ n $ over the alphabet $ \{a, b, \dots, z\} $. **Constraints** $ 3 \leq n \leq 100 $ All characters in $ s $ are lowercase Latin letters. **Objective** Find the minimum number of characters to remove from $ s $ such that the resulting string contains no substring equal to "xxx". Equivalently, for every contiguous substring of three characters, at least one character must be removed from every run of three or more consecutive 'x' characters. Let $ r $ be the number of consecutive 'x' characters in a maximal run of 'x's in $ s $. For each such run of length $ r \geq 3 $, the minimum number of 'x's to remove is $ \max(0, r - 2) $. **Objective Function** Let $ R = \{ r_1, r_2, \dots, r_m \} $ be the lengths of all maximal contiguous runs of the character 'x' in $ s $. Then the minimum number of characters to remove is: $$ \sum_{r_i \in R} \max(0, r_i - 2) $$

Samples

Input #1

6
xxxiii

Output #1

Input #2

5
xxoxx

Output #2

Input #3

10
xxxxxxxxxx

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. File Name",
    "description": {
      "content": "You can not just take the file and send it. When Polycarp trying to send a file in the social network \"Codehorses\", he encountered an unexpected problem. If the name of the file contains three or more",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF978B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You can not just take the file and send it. When Polycarp trying to send a file in the social network \"Codehorses\", he encountered an unexpected problem. If the name of the file contains three or more...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你不能直接取文件并发送。当 Polycarp 尝试在社交网络 \"Codehorses\" 中发送文件时，遇到了一个意外的问题。如果文件名中包含三个或更多连续的 \"_x_\"（小写拉丁字母 \"_x_\"），系统会认为文件内容与社交网络主题不符。此时，文件将不被发送，并显示错误信息。\n\n请确定最少需要从文件名中删除多少个字符，使得删除后文件名中不再包含 \"_xxx_\" 作为子串。如果文件名初始时就不包含禁止...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the string.  \nLet $ s = s_1 s_2 \\dots s_n $ be a string of length $ n $ over the alphabet $ \\{a, b, \\dots, z\\} $.\n\n**Constraints**  \n$ 3 \\le...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments