Problem

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

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

Example 2:

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

Constraints:

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

My code

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        dummy = {}
        for i, l in enumerate (s):
            dummy[l] = i
        
        stack=[]
        seen=set()
        
        for j,m in enumerate(s):
            if m in seen:
                continue
            while stack and stack[-1]>m and j < dummy[stack[-1]] :
                seen.remove(stack[-1])
                stack.pop()
                
            stack.append(m)
            seen.add(m)
            
        return ''.join(stack)

Review

[실행 결과]
Runtime 32 ms
Memory 14.3 MB

[접근법]
enumerate를 사용해서 알파벳을 인덱스로 갖는 리스트를 생성한다
실제 인덱스값과 리스트 안의 인덱스값을 비교하며 위치를 조정한다
만약 이미 봤던 값이라면 (seen안의 값) 위 단계를 건너뛴다.
모든 단어에 대해 반복한다.

[느낀점]
도대체stack[-1]>m 처럼 글자의 크기를 비교하는 생각은 누가 한 걸까...?
문제를 이해하는데도 너무 어려웠어서 답지 봄 :두_눈: