[leetcode] 1081. Smallest Subsequence of Distinct Characters

[leetcode] 1081. Smallest Subsequence of Distinct Characters

Description

Return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Note: This question is the same as 316: 1:

Input: s = "bcabc"Output: "abc"

Example 2:

Input: s = "cbacdcbc"Output: "acdb"

Constraints:

1 <= s.length <= 1000s consists of lowercase English letters.

分析

题目的意思是：求出字符串的最小子序列，其中子序列中每个字符唯一，并且包含字符串所有不同的字符。这道题我看了一下别人的实现，需要用到栈来实现，首先把每个字符的最后一个位置的索引存放在last字典中。

在遍历的时候，如果当前的值小于栈最后一个值的话，还要看栈里面的值是否到达了字符串该字母的最后一个位置了，这时候就需要用上last字典了，如果已经到达了该字母的最后一个位置了，就不能把该字母出栈了，否则该字母出栈。对于与栈里重复的字符，选择跳过就行了。 最后的结果就是把栈里面的字符拼接就可以了。

代码

class Solution: def smallestSubsequence(self, s: str) -> str: stack=[] last={} for i in range(len(s)): last[s[i]]=i for i,ch in enumerate(s): if(ch in stack): continue while(stack and stack[-1]>ch and i

参考文献

​​[LeetCode] [Java/C++/Python] Stack Solution O(N)​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。