C. Alphabetic Removals

Codeforces

IDCF999C

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

You are given a string $s$ consisting of $n$ lowercase Latin letters. Polycarp wants to remove exactly $k$ characters ($k \le n$) from the string $s$. Polycarp uses the following algorithm $k$ times: * if there is at least one letter '_a_', remove the leftmost occurrence and stop the algorithm, otherwise go to next item; * if there is at least one letter '_b_', remove the leftmost occurrence and stop the algorithm, otherwise go to next item; * ... * remove the leftmost occurrence of the letter '_z_' and stop the algorithm. This algorithm removes a single letter from the string. Polycarp performs this algorithm exactly $k$ times, thus removing exactly $k$ characters. Help Polycarp find the resulting string. ## Input The first line of input contains two integers $n$ and $k$ ($1 \le k \le n \le 4 \cdot 10^5$) — the length of the string and the number of letters Polycarp will remove. The second line contains the string $s$ consisting of $n$ lowercase Latin letters. ## Output Print the string that will be obtained from $s$ after Polycarp removes exactly $k$ letters using the above algorithm $k$ times. If the resulting string is empty, print nothing. It is allowed to print nothing or an empty line (line break). [samples]

[{"iden":"statement","content":"你被给定一个由 $n$ 个小写拉丁字母组成的字符串 $s$。Polycarp 想要从字符串 $s$ 中恰好移除 $k$ 个字符（$k lt.eq n$）。Polycarp 使用以下算法重复 $k$ 次：\n\n该算法从字符串中移除一个字母。Polycarp 恰好执行此算法 $k$ 次，从而移除恰好 $k$ 个字符。\n\n帮助 Polycarp 找到最终得到的字符串。\n\n输入的第一行包含两个整数 $n$ 和 $k$（$1 lt.eq k lt.eq n lt.eq 4 dot.op 10^5$）——字符串的长度和 Polycarp 将移除的字母数量。\n\n第二行包含由 $n$ 个小写拉丁字母组成的字符串 $s$。\n\n请输出在 Polycarp 使用上述算法恰好移除 $k$ 个字母后得到的字符串。\n\n如果结果字符串为空，请不要输出任何内容。允许不输出任何内容或仅输出一个空行（换行符）。"},{"iden":"input","content":"输入的第一行包含两个整数 $n$ 和 $k$（$1 lt.eq k lt.eq n lt.eq 4 dot.op 10^5$）——字符串的长度和 Polycarp 将移除的字母数量。第二行包含由 $n$ 个小写拉丁字母组成的字符串 $s$。"},{"iden":"output","content":"请输出在 Polycarp 使用上述算法恰好移除 $k$ 个字母后得到的字符串。如果结果字符串为空，请不要输出任何内容。允许不输出任何内容或仅输出一个空行（换行符）。"},{"iden":"examples","content":"输入1\n15 3\ncccaabababaccbc\n输出1\ncccbbabaccbc\n\n输入2\n15 9\ncccaabababaccbc\n输出2\ncccccc\n\n输入3\n1 1\nu\n输出3\n"}}]

Given a string $ s $ of length $ n $ and an integer $ k $ such that $ 1 \leq k \leq n \leq 4 \cdot 10^5 $, remove exactly $ k $ characters from $ s $ using the following greedy algorithm: At each of the $ k $ steps, remove the first character $ s[i] $ such that $ s[i] > s[i+1] $ (i.e., the first local maximum). If no such character exists, remove the last character. Formally, define the removal process as a sequence of $ k $ operations: Let $ s^{(0)} = s $, and for $ j = 1 $ to $ k $: - Find the smallest index $ i \in \{0, 1, \dots, |s^{(j-1)}| - 2\} $ such that $ s^{(j-1)}[i] > s^{(j-1)}[i+1] $. - If such an $ i $ exists, set $ s^{(j)} = s^{(j-1)}[0:i] + s^{(j-1)}[i+1:] $. - Otherwise, set $ s^{(j)} = s^{(j-1)}[0:|s^{(j-1)}|-1] $. Output $ s^{(k)} $.

Samples

Input #1

15 3
cccaabababaccbc

Output #1

cccbbabaccbc

Input #2

15 9
cccaabababaccbc

Output #2

cccccc

API Response (JSON)

{
  "problem": {
    "name": "C. Alphabetic Removals",
    "description": {
      "content": "You are given a string $s$ consisting of $n$ lowercase Latin letters. Polycarp wants to remove exactly $k$ characters ($k \\le n$) from the string $s$. Polycarp uses the following algorithm $k$ times: ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF999C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string $s$ consisting of $n$ lowercase Latin letters. Polycarp wants to remove exactly $k$ characters ($k \\le n$) from the string $s$. Polycarp uses the following algorithm $k$ times:\n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"你被给定一个由 $n$ 个小写拉丁字母组成的字符串 $s$。Polycarp 想要从字符串 $s$ 中恰好移除 $k$ 个字符（$k lt.eq n$）。Polycarp 使用以下算法重复 $k$ 次：\\n\\n该算法从字符串中移除一个字母。Polycarp 恰好执行此算法 $k$ 次，从而移除恰好 $k$ 个字符。\\n\\n帮助 Pol...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given a string $ s $ of length $ n $ and an integer $ k $ such that $ 1 \\leq k \\leq n \\leq 4 \\cdot 10^5 $, remove exactly $ k $ characters from $ s $ using the following greedy algorithm:  \n\nAt each o...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments