[LeetCode] 316 | Remove Duplicate Letters | Python

---

문제 링크: https://leetcode.com/problems/remove-duplicate-letters/

---

문제

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.

---

조건

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

---

내 풀이

먼저 s안에 각 알파벳의 빈도수를 리스트(count)에 저장한다.

리스트 check는 해당 알파벳이 ans에 존재하는지 여부를 판단하는 용이다.

그 후에 아래 알고리즘을 적용하면 된다.

 

(1) 현재 보고있는 글자가 리턴할 문자열(ans)에 존재하지 않고, (2) ans의 마지막 글자가 현재 보고있는 글자보다 뒷 순서고, (3) 주어진 문자열(s)의 현재 보고있는 위치의 뒷부분에도 존재하면 마지막 글자를 삭제한다.

 

이렇게 하면 lexicographical order를 지킬 수 있다.

---

코드

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        count, check = [0 for _ in range(26)], [False for _ in range(26)]
        ans = []
        
        for char in s:
            count[ord(char)-ord('a')] += 1
        
        for char in s:
            idx = ord(char)-ord('a')
            count[idx] -= 1
            
            if not check[idx]:
                while len(ans) > 0 and ans[-1] > char and count[ord(ans[-1])-ord('a')] > 0:
                    check[ord(ans[-1])-ord('a')] = False
                    del ans[-1]
                
                ans.append(char)
                check[idx] = 1
        
        return ''.join(ans)