Daily classic

Spring Outlook by Du Fu (Tang dynasty)

The country broken mountains and rivers in the city spring vegetation deep.

Feeling flowers splash tears, hate don’t bird startled.

Beacon fire even in March, the letter is worth ten thousand gold.

Hoary hair scratch shorter, hun hun hairpin.

describe

Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Example 1:

Input: s = "bcabc"
Output: "abc"
Copy the code

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"
Copy the code

Note:

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

parsing

Given a string s, return the lexicographical smallest sequence of s, in which all the different characters containing s are exactly once. To keep the lexicographical order as small as possible, arrange the characters in alphabetical order, and include all the characters that occur.

We can traverse characters from left to right in order, putting characters into a monochromatic sequence of increasing characters Q, so as to keep the lexicographical order as small as possible. If a character has been traversed, we go directly to the next character traversal; If not, determine whether the character at the top of the stack will appear later and the character at the top of the stack is larger than the current character. If so, remove the character at the top of the stack of Q all the time, handle according to the above ideas, and return the final q into a string.

answer

class Solution(object):
    def smallestSubsequence(self, text):
        """
        :type s: str
        :rtype: str
        """
        d = collections.defaultdict(int)
        for c in text:
            d[c] += 1
        s = set()
        q = []
        for c in text:
            d[c] -= 1
            if c not in s:
                while q and d[q[-1]]>0 and q[-1]>c:
                    s.remove(q.pop())
                q.append(c)
                s.add(c)
        return ''.join(q)
                    
        
        	      
		
Copy the code

The results

Runtime: 10 MS, faster than 51.85% of Python online submissions for particle Subsequence of Distinct Characters. Memory Usage: Given in the Python online list for arguments with Distinct Characters.Copy the code

Original link: leetcode.com/problems/sm…

Your support is my biggest motivation