A. Homework

Codeforces

IDCF101A

Time2000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

Once when Gerald studied in the first year at school, his teacher gave the class the following homework. She offered the students a string consisting of _n_ small Latin letters; the task was to learn the way the letters that the string contains are written. However, as Gerald is too lazy, he has no desire whatsoever to learn those letters. That's why he decided to lose some part of the string (not necessarily a connected part). The lost part can consist of any number of segments of any length, at any distance from each other. However, Gerald knows that if he loses more than _k_ characters, it will be very suspicious. Find the least number of distinct characters that can remain in the string after no more than _k_ characters are deleted. You also have to find any possible way to delete the characters. ## Input The first input data line contains a string whose length is equal to _n_ (1 ≤ _n_ ≤ 105). The string consists of lowercase Latin letters. The second line contains the number _k_ (0 ≤ _k_ ≤ 105). ## Output Print on the first line the only number _m_ — the least possible number of different characters that could remain in the given string after it loses no more than _k_ characters. Print on the second line the string that Gerald can get after some characters are lost. The string should have exactly _m_ distinct characters. The final string should be the subsequence of the initial string. If Gerald can get several different strings with exactly _m_ distinct characters, print any of them. [samples] ## Note In the first sample the string consists of five identical letters but you are only allowed to delete 4 of them so that there was at least one letter left. Thus, the right answer is 1 and any string consisting of characters "_a_" from 1 to 5 in length. In the second sample you are allowed to delete 4 characters. You cannot delete all the characters, because the string has length equal to 7. However, you can delete all characters apart from "_a_" (as they are no more than four), which will result in the "_aaaa_" string. In the third sample you are given a line whose length is equal to 8, and _k_ = 10, so that the whole line can be deleted. The correct answer is 0 and an empty string.

当杰拉尔德上小学一年级时，老师给全班布置了如下作业：给出一个由 #cf_span[n] 个小写拉丁字母组成的字符串，任务是学习该字符串中包含的字母是如何书写的。然而，由于杰拉尔德太懒，他完全不想学习这些字母。因此，他决定删除字符串的一部分（不一定是连续的部分）。删除的部分可以包含任意数量、任意长度、任意位置的段。但杰拉尔德知道，如果他删除超过 #cf_span[k] 个字符，就会非常可疑。求在删除不超过 #cf_span[k] 个字符后，字符串中可能剩余的最少不同字符数。同时，你需要找出一种删除字符的可能方式。第一行输入一个长度为 #cf_span[n] 的字符串（#cf_span[1 ≤ n ≤ 10^5]），该字符串由小写拉丁字母组成。第二行包含数字 #cf_span[k]（#cf_span[0 ≤ k ≤ 10^5]）。在第一行输出一个数字 #cf_span[m] —— 在删除不超过 #cf_span[k] 个字符后，剩余字符串中可能的最少不同字符数。在第二行输出杰拉尔德删除某些字符后能得到的字符串。该字符串必须恰好包含 #cf_span[m] 个不同字符，且必须是原字符串的子序列。如果杰拉尔德能得到多个恰好包含 #cf_span[m] 个不同字符的字符串，请输出其中任意一个。在第一个样例中，字符串由五个相同的字母组成，但你只能删除其中四个，因此至少要保留一个字母。因此正确答案是 1，任何由 1 到 5 个字符 "_a_" 组成的字符串均可。在第二个样例中，你被允许删除 4 个字符。你不能删除所有字符，因为字符串长度为 7。但你可以删除除 "_a_" 以外的所有字符（因为它们不超过四个），从而得到字符串 "_aaaa_"。在第三个样例中，你得到一个长度为 8 的字符串，且 #cf_span[k = 10]，因此整个字符串可以被删除。正确答案是 0 和一个空字符串。 ## Input 第一行输入一个长度为 #cf_span[n] 的字符串（#cf_span[1 ≤ n ≤ 10^5]），该字符串由小写拉丁字母组成。第二行包含数字 #cf_span[k]（#cf_span[0 ≤ k ≤ 10^5]）。 ## Output 在第一行输出一个数字 #cf_span[m] —— 在删除不超过 #cf_span[k] 个字符后，剩余字符串中可能的最少不同字符数。在第二行输出杰拉尔德删除某些字符后能得到的字符串。该字符串必须恰好包含 #cf_span[m] 个不同字符，且必须是原字符串的子序列。如果杰拉尔德能得到多个恰好包含 #cf_span[m] 个不同字符的字符串，请输出其中任意一个。 [samples] ## Note 在第一个样例中，字符串由五个相同的字母组成，但你只能删除其中四个，因此至少要保留一个字母。因此正确答案是 1，任何由 1 到 5 个字符 "_a_" 组成的字符串均可。在第二个样例中，你被允许删除 4 个字符。你不能删除所有字符，因为字符串长度为 7。但你可以删除除 "_a_" 以外的所有字符（因为它们不超过四个），从而得到字符串 "_aaaa_"。在第三个样例中，你得到一个长度为 8 的字符串，且 #cf_span[k = 10]，因此整个字符串可以被删除。正确答案是 0 和一个空字符串。

**Definitions** Let $ s \in \Sigma^* $ be the input string of length $ n $, where $ \Sigma $ is the set of lowercase Latin letters. Let $ k \in \mathbb{Z}_{\geq 0} $ be the maximum number of characters that can be deleted. Let $ f(c) $ denote the frequency of character $ c \in \Sigma $ in $ s $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 0 \leq k \leq 10^5 $ 3. $ s $ consists only of lowercase Latin letters. **Objective** Find the minimum number $ m \in \mathbb{Z}_{\geq 0} $ of distinct characters that can remain in $ s $ after deleting at most $ k $ characters, and construct a subsequence of $ s $ with exactly $ m $ distinct characters. To minimize $ m $, greedily remove characters with the smallest frequencies first. Let $ F = \{ f(c) \mid c \in \text{distinct characters in } s \} $, sorted in non-decreasing order. Let $ r = k $ (remaining deletions). Iteratively subtract $ f(c) $ from $ r $ for each character $ c $ in order of increasing frequency, until $ r < f(c) $ or no characters remain. Then $ m $ is the number of distinct characters not removed. Construct the result string by keeping all occurrences of the remaining distinct characters in their original order. **Output** - First line: $ m $ - Second line: a subsequence of $ s $ containing exactly $ m $ distinct characters, formed by retaining all instances of the $ m $ least-frequent-to-remove characters' complements.

Samples

Input #1

aaaaa
4

Output #1

1
aaaaa

Input #2

abacaba
4

Output #2

1
aaaa

Input #3

abcdefgh
10

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Homework",
    "description": {
      "content": "Once when Gerald studied in the first year at school, his teacher gave the class the following homework. She offered the students a string consisting of _n_ small Latin letters; the task was to learn ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF101A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Once when Gerald studied in the first year at school, his teacher gave the class the following homework. She offered the students a string consisting of _n_ small Latin letters; the task was to learn ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "当杰拉尔德上小学一年级时，老师给全班布置了如下作业：给出一个由 #cf_span[n] 个小写拉丁字母组成的字符串，任务是学习该字符串中包含的字母是如何书写的。然而，由于杰拉尔德太懒，他完全不想学习这些字母。因此，他决定删除字符串的一部分（不一定是连续的部分）。删除的部分可以包含任意数量、任意长度、任意位置的段。但杰拉尔德知道，如果他删除超过 #cf_span[k] 个字符，就会非常可疑。\n\n求在...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^* $ be the input string of length $ n $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the maximum number of chara...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments