算法随笔_64: 含特定字母的最小子序列

上一篇:算法随笔_63: 子数组范围和-CSDN博客

=====

题目描述如下:

给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。

返回 s 中长度为 k 且 字典序最小 的子序列，该子序列同时应满足字母 letter 出现 至少 repetition 次。生成的测试用例满足 letter 在 s 中出现 至少 repetition 次。

子序列 是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。

字符串 a 字典序比字符串 b 小的定义为：在 a 和 b 出现不同字符的第一个位置上，字符串 a 的字符在字母表中的顺序早于字符串 b 的字符。

示例 1：

输入：s = "leet", k = 3, letter = "e", repetition = 1
输出："eet"
解释：存在 4 个长度为 3 ，且满足字母 'e' 出现至少 1 次的子序列：
- "lee"（"leet"）
- "let"（"leet"）
- "let"（"leet"）
- "eet"（"leet"）
其中字典序最小的子序列是 "eet" 。

=====

算法思路:

我们这里用e代表题目中的letter以方便描述。由于题目要求的条件比较多，我们先考虑简单的情况，即，如何找到 s 中长度为 k 且字典序最小的子序列。

对于所有长度为k的子序列，第一个字符肯定要是字典序最小的。如果有多个子序列，它们的第一个字符字典序最小且相同，那么我们需要从它们当中找出第二个字符字典序最小的那些序列。以此类推，直到找出符合条件的子序列。

其实这就是要求我们从原字符串中找出: 最小字符，次小字符，第三小字符，等等，这样一个字符串，且它们的索引必须是递增的。因此我们可以使用“栈”的数据结构来找出它们。算法如下:

1. 我们设数组res做为此栈。设s_len为s的长度。

2. 然后我们从左往右枚举原字符串s。只要s[i] < res[-1]，我们弹出栈顶元素res[-1]。重复此判断直到s[i] >= res[-1]。我们把s[i]放入res。

注: 由于我们需要维持总长度k，所以在步骤2中有时不能把res里的元素全部弹出，需要保证以下不等式成立:

(res长度+ [i, n-1]长度) >= k

对于不能弹出的情况，直接把s[i]放入res。

枚举完成后，res中存储的就是: 最小字符，次小字符，第三小字符，等等，这样一个字符串，且它们的索引是递增的。如果res长度大于k，我们取res中的前k个元素即为最终答案。

好了，到此时，我们就解决了题目中的一个条件。下面，我们再来看如何满足其他条件。题目还要求字母 letter 出现 至少 repetition 次。

我们发现答案中的第一个字符不可能取在倒数第repetition个e之后，因为那样的话，最后的结果e数肯定少于repetition。因此我们需要先找到倒数第repetition个e的索引，把它做为一个判断的基准，我们设变量eKeyInd来储存这个值。那么在eKeyInd之前的字符串也尽量要找出，最小字符，次小字符，第三小字符，等等。和上面的算法原理一样。

为了方便后面描述，我们再设两个变量:

eResCnt: 表示已经在res中的e的数量。

eLeftCnt: 表示eKeyInd之后还剩下e的数量，包括eKeyInd处的e。初始值为repetition。

在枚举到eKeyInd时，res会有两种情况:

1. res长度+eLeftCnt >= k，这时我们取res的前(k-eLeftCnt)个字符，然后加上eLeftCnt个e即为最终的答案。

2. res长度+eLeftCnt < k，由于不足以形成k个字符，因此我们需要从eKeyInd到下一个e出现的索引中间再尝试找出一段递增的字符串。这样形成一个新的res。由于eKeyInd处的e已经添加进去res，因此eLeftCnt需要减1。然后重复判断这两种情况，直至找出答案。

在弹出栈顶的过程中，如果碰到栈顶res[-1]字符为e时，我们还需要确保eResCnt+eLeftCnt>repetition。这样才能弹出e，且eResCnt要减1。否则不能弹出e。

同时，在入栈时，如果当前字符为e，也要相应把eResCnt加1。

对于额外的条件满足，算法总体的思路就是上面提到的两种情况。其他的地方就是要注意一些细节的判断，以保证最后算法的准确。

算法的时间复杂度为O(n)。下面是Python代码实现:

class Solution(object):def smallestSubsequence(self, s, k, letter, repetition):""":type s: str:type k: int:type letter: str:type repetition: int:rtype: str"""s_len=len(s)res=[]eKeyInd=0eLeftCnt=0eResCnt=0for i in range(s_len-1, -1, -1):if s[i]==letter:eLeftCnt+=1if eLeftCnt==repetition:eKeyInd=ibreakfor i in range(s_len):while res and s[i]<res[-1] and len(res)+s_len-i > k:if res[-1]==letter:if eResCnt+eLeftCnt==repetition:breakelse:eResCnt-=1res.pop()if s[i]==letter and i>=eKeyInd:if len(res)+eLeftCnt>=k:breakelse:eLeftCnt-=1res.append(s[i])if s[i]==letter:eResCnt+=1res=res[:k-eLeftCnt]+[letter]*eLeftCntres="".join(res)return res

关键词: 单调栈