蓝桥杯2024年第十五届决赛真题-最小字符串

给定一个长度为 N 且只包含小写字母的字符串 S，和 M 个小写字母c₁, c₂, . . . , c_M。现在你要把 M 个小写字母全部插入到字符串 S 中，每个小写字母都可以插入到任意位置。

请问能得到的字典序最小的字符串是什么？

第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串 S。

第三行包含 M 个小写字母 c₁, c₂, . . . , c_M。

输出一个长度为 N + M 的字符串代表答案。

4 3
abbc
cba

aabbbcc

【评测用例规模与约定】

对于 20% 的评测用例，M = 1。对于 100% 的评测用例，1 ≤ N, M ≤ 10⁵。