Python에서 고유한 문자의 가장 작은 부분 시퀀스

텍스트가 있다고 가정하고 텍스트의 모든 고유한 문자를 정확히 한 번 포함하는 사전순으로 가장 작은 텍스트 하위 시퀀스를 찾아야 합니다. 따라서 입력이 "cdadbcc"와 같으면 출력은 "adbc"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• stack st를 정의하고 두 개의 맵을 last_o로 간주하고 처음에는 비어 있음
• i의 경우 텍스트 길이 범위 - 1에서 0까지
  • text[i]가 last_o에 없는 경우 -
    • last_o[text[i]] :=나
    • 고려[text[i]] :=거짓
  • i :=0
  • 동안 i <텍스트의 길이
    • 스택에 요소가 없는 경우
      • 텍스트[i]를 스택에 푸시
      • 고려[text[i]]:=사실
      • i를 1 증가
    • 그렇지 않으면 스택 상단> text[i] 및 고려된[text[i]]가 false
      • if last_o[스택 탑]> i
        • 고려됨[스택 상단 요소] :=false
        • 스택에서 팝
      • 그렇지 않으면
        • 고려[tex[i]] =사실
        • 텍스트[i]를 스택에 삽입
        • i를 1 증가
    • 그렇지 않으면 스택 상단 요소
    • 텍스트[i]를 스택에 삽입
    • 고려[text[i]]:=사실
    • i를 1 증가
  • 그렇지 않으면 i를 1만큼 증가

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class Solution(object):
   def smallestSubsequence(self, text):
      """
      :type text: str
      :rtype: str
      """
      stack = []
      last_o = {}
      considered = {}
      for i in range(len(text)-1,-1,-1):
         if text[i] not in last_o:
            last_o[text[i]] = i
            considered[text[i]] = False
      print(last_o)
      i = 0
      while i < len(text):
         print(stack,i,text[i])
         if len(stack) == 0:
            stack.append(text[i])
            considered[text[i]] = True
            i+=1
         elif stack[-1]>text[i] and considered[text[i]] == False:
            if last_o[stack[-1]]>i:
               considered[stack[-1]]=False
               stack.pop()
            else:
               considered[text[i]] = True
               stack.append(text[i])
               i+=1
         elif stack[-1]<text[i] and considered[text[i]] == False:
            stack.append(text[i])
            considered[text[i]] = True
            i+=1
         else:
            i+=1
      return "".join(i for i in stack)

입력

"cdadabcc"

출력

"adbc"