← 返回题目列表

Codeforces · 101/A

A. 家庭作业

中文机器翻译题面 查看原题

有一次,当杰拉德在学校一年级学习时,他的老师给全班布置了以下作业。她给学生们提供了一个由 n 个小拉丁字母组成的字符串;任务是学习字符串中包含的字母的书写方式。然而,由于杰拉德太懒了,他根本没有兴趣学习这些字母。这就是为什么他决定丢失字符串的某些部分(不一定是连接的部分)。丢失的部分可以由任意数量、任意长度、彼此距离任意的段组成。然而,杰拉德知道,如果他丢失了超过 k 个字符,那就非常可疑了。

求删除不超过 k 个字符后,字符串中可以保留的最少不同字符数。您还必须找到任何可能的方法来删除字符。

输入

第一个输入数据行包含一个长度等于 n (1 ≤ n ≤ 105) 的字符串。该字符串由小写拉丁字母组成。第二行包含数字 k (0 ≤ k ≤ 105)。

输出

在第一行打印唯一的数字 m — 在给定字符串丢失不超过 k 个字符后,可以保留在给定字符串中的不同字符的最少可能数量。

在第二行打印Gerald丢失一些字符后得到的字符串。该字符串应该恰好有 m 个不同的字符。最终字符串应该是初始字符串的子序列。如果 Gerald 可以得到几个具有恰好 m 个不同字符的不同字符串,则打印其中的任何一个。

示例

输入 #1

aaaaa
4

输出 #1

1
aaaaa

输入 #2

abacaba
4

输出 #2

1
aaaa

输入 #3

abcdefgh
10

输出 #3

0

注意

在第一个示例中,字符串由 5 个相同的字母组成,但您只能删除其中 4 个,以便至少剩下一个字母。因此,正确答案是 1 以及长度为 1 到 5 的字符“a”组成的任何字符串。

在第二个示例中,您可以删除 4 个字符。您无法删除所有字符,因为该字符串的长度等于 7。但是,您可以删除除“a”之外的所有字符(因为它们不超过四个),这将得到“aaaa”字符串。

在第三个示例中,您将得到一条长度等于 8 的线,并且 k = 10,因此可以删除整条线。正确答案是 0 和空字符串。