Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q21

Q21 Remove Duplicate Letters

Q

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.

Sample Input

Input: s = “bcabc”
Output: “abc”

Input: s = “cbacdcbc”
Output: “acdb”

Constraints

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

1. Given Solution #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        #sort the set of s (to start from alphabetical order)
        for char in sorted(set(s)):
            suffix = s[s.index(char):]
            
            #전체 집합과 접미사 집합이 일치할 경우 분리한다
            if set(s) == set(suffix):
                return char + self.removeDuplicateLetters()
        return ''
        

a = Solution()
s = "cbacdcbc"
print(a.removeDuplicateLetters(s))

Introducing the concept, suffix and set, this solution simply solved the problem. Let’s start from the top.

  1. sorted(set(s)) : by using set, duplicated letters are all eliminated and lose their order. Sort them in alphabetical order by using sorted(). In the case “s = cbacdcbc”, sorted(set(s)) is (a,b,c,d).
  2. Define suffix as string, start from ‘char’ to the end. In the first loop (when char is ‘a’), suffix is acdcbc.
  3. Check if suffix contains all alphabet in the set(s). If not, repeat the loop. If so, separate char from the suffix, because it will be the first letter of lexicographical order. Then do recursion with the suffix that ‘char’ is eliminated.
  4. Repeat this until set(s) became empty, and return ‘’(=None) instead of doing recursion.
  5. Gradually trace back to the first recursion and return fully joined letter which is ordered lexicographically.

**보충 설명 : 알파벳 순서대로 대입해보며 계속 제거해간다. 제거할 수 없는 경우(제거해버리면 set가 일치하지 않는 경우)에는 사전적 배열에서 조금 뒤로 밀리는 것을 감수하고, 다음 알파벳을 대입한다. 이 과정을 반복한다. 제거된 알파벳들은 제거된 순서대로 앞 자리에 오게 된다. 재귀가 끝나면 none을 return하는데, 이를 기점으로 차례로 뒤에서부터 앞으로 단어들을 합쳐 나간다(return char + func(suffix without char)). 결국에는 중복이 제거되고 사전적으로 배열된 단어가 리턴.

2. Given Solution #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter, seen, stack = collections.Counter(s), set(), []

        for char in s:
            counter[char] -= 1
            if char in seen:
                continue
            
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                seen.remove(stack.pop())
            stack.append(char)
            seen.add(char)
        
        return ''.join(stack)        

a = Solution()
s = "cbacdcbc"
print(a.removeDuplicateLetters(s))

Repeat steps for all the letters of the input string. Each letter passes through the following steps.

  1. counter[char] -= 1 : subtract 1 from the counter. This is for the decision whether the element(=char) appears afterward or not.
  2. When char is already in the set, seen, passes the loop.
  3. Until the case that ① stack exists ② input(=char) is smaller than the last element ③ the last element appears afterward, keep extracting the last element from the set and the stack.
  4. Add char to the set and the stack.
  5. After these loops, return the joined stack.

** 보충 설명 : 매번 알파벳이 들어올 때, 앞에 있었던 것들을 쳐내도 될지 매번 검증하는 방식이다. 들어오는 순서대로 차곡 차곡 쌓되, 들어오는 순간 마지막 원소보다 큰지 작은지, 마지막 원소를 pop해도 나중에 다시 등장해서 뒤에 붙는지를 체크한다.

사전식 배열은 char < stack[-1]를 통해 구현하고, 뒤에 다시 붙일 수 있는지는 counter[stack[-1]] >0으로 확인한다.

while문을 쓴 이유는, 새로운 원소가 들어올 때 앞의 모든 값에 대해서 검증해야하기 때문이다. ‘azxbzx’라는 input을 받았을 때, a z x까지는 stack이 순조롭게 쌓이다가 b를 받는 순간 1)앞의 원소들은 뒤에 다시 등장 2)b는 z랑 x보다 작음 을 만족하므로 a에 닿을 때까지 계-속 추출해낸다.

seen이라는 set를 도입한 이유는, 기존까지는 들어오지 않았던 새로운 값에 대해서만 검증이 이루어져야하기 때문이다. 이를 생략하지 않으면 while loop 뒤의 stack.append와 seen.add에 따라 stack에 중복으로 값이 쌓이게 될 수 있다.

Overall Review

Solving problems with stack-algorithm is too strange to me. Once again, I’m experiencing that stack itself is really easy concept but utilizing this method when solving problems is not that easy. When struggling to solve the problem using stack, only abstract idea comes out. A lot more time for studying will be required to handle stack-algorithm perfectly.

참고