给定长度为 m 的序列 T ,求一个长度为 n 且字典序最小的排列.并且要求序列 T 为所求排列的子序列.题目保证这样的排列一定存在. S 是 T 的子序列,当且仅当 S 是 T 通过删除任意数量元素所得到的.

这是一个经典的问题，可以使用贪心算法解决。首先将序列 T 中的元素按照字典序从小到大进行排序，然后依次取出其中的元素，将其从序列 T 中删除，并添加到新的排列中，直到新排列的长度达到 n 。如果此时序列 T 已经被取空，则在新排列后继续添加字典序最小的元素直至长度为 n 。这样得到的新排列即为所求排列。

相关问题

给定字符串 s， 其特征子序列 t 满足： 子序列中的字符各不相同； s 中的各种字符都能在 t 中找到； 对于一个字符串 s，可能会对应多个特征子序列，其中字典序最小的特征序列称为“最优特征子序列”。 请写一个程序，返回字符串的最优特征子序列。要求时间复杂度不超过 O(N)。要求输入一行长度为N。然后输入一行长度为N的s字符串。输出要求的最优特征子序列。

我们可以用贪心算法来解决这个问题。我们从左到右遍历字符串 s，对于每一个字符，如果它在特征子序列 t 中出现过，我们就跳过它；否则，我们将它加入到特征子序列 t 中，并将 t 中所有比它大的字符都从 t 中删除。

具体来说，我们可以用一个桶来记录每个字符是否在 t 中出现过。对于每个字符，我们检查它是否在桶中出现过，如果出现过，我们就跳过它；否则，我们将它加入到 t 的末尾，并从 t 的末尾开始删除所有比它大的字符。

时间复杂度为 O(N)，因为我们只需要遍历一遍字符串 s，并且桶的大小是固定的，与字符串长度无关。

以下是 Python 代码实现：

n = int(input())
s = input()

t = []
seen = [False] * 26
for c in s:
    idx = ord(c) - ord('a')
    if not seen[idx]:
        while t and t[-1] > c and s.find(t[-1], s.find(c)+1) != -1:
            seen[ord(t[-1]) - ord('a')] = False
            t.pop()
        t.append(c)
        seen[idx] = True

print(''.join(t))

给定一个长度为n仅由小写字母组成的字符串s,我们需要找到一个长度为k的字符串t,要求t的所有字母的集合是s的所有字母集合的一个子集且s的字典序小于t的字典序。且字符串t是所有满足以上情况下的字符串中字典序最小。集合中的元素不会重复。

先统计出字符串s中的所有字母，然后将它们按照字典序从小到大排序，得到一个字母集合。设这个集合的大小为a。

我们可以从左往右依次构造字符串t。我们先将t的前面k-a个位置填上排好序的字母集合中的字母，然后用字典序最小的字母来填充剩下的位置。这样就得到了一个长度为k的字符串t。

如果s的字典序比t小，那么t就是我们要找的字符串。否则，我们需要调整t的字母序列。

我们从右往左扫描t，找到第一个可以往后替换的位置i。如果不存在这样的位置，说明t已经是字典序最小的字符串了，直接返回t即可。否则，我们将位置i上的字母替换成它后面剩余字母中最小的一个字母，然后将i后面的所有字母按字典序排序，得到一个新的字母序列。最后将新的字母序列填充到t的后面k-i-1个位置上，就得到了一个新的字符串t1。

如果s的字典序小于t1，那么t1就是我们要找的字符串。否则，我们需要重复上面的步骤，直到找到一个合法的字符串为止。

时间复杂度分析：字符串的长度为n，字母集合的大小为a，构造t的时间复杂度为O(n+a)，调整t的时间复杂度为O(a log a + (k-a-1) log (k-a-1))，每次调整后，t的长度都会增加1，因此总的时间复杂度为O(n log n + k log k)。