[파이썬 알고리즘 인터뷰]

(12) Remove Duplicate Letters

 

github.com/onlybooks/algorithm-interview

★★ Normal

( 책이랑 사이트랑 조금 난이도 차가 있는..?)

 

[LeetCode]

Remove Duplicate Letters - LeetCode

 

---

풀이법

 처음에 문제를 잘못 이해해서, 홀 짝수로 풀려고했다. .. 

책에서도 문제를 이해하는 것이 더 어려운 문제라고 했다.order도 고려하면서 중복제거를 하는 문제였다.

다만, seen 변수를 두어서 검색용으로 사용하고 stack은 딱 pop, append만 하게 분리해놨다.

onlybooks/algorithm-interview

Java

import java.util.Stack;

class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        HashSet<Character> seen = new HashSet<>();
        Map<Character, Integer> counts = new HashMap<>();

        for (char c : s.toCharArray())
            counts.merge(c, 1, Integer::sum);

        for (char c : s.toCharArray()) {
            counts.put(c, counts.get(c) - 1);

            if (seen.contains(c))
                continue;

            while(!stack.empty() && stack.peek() > c && counts.get(stack.peek()) > 0)
                seen.remove(stack.pop());

            stack.add(c);
            seen.add(c);
        }
        StringBuilder sb = new StringBuilder();
        
        while(!stack.isEmpty())
            sb.insert(0, stack.pop());
        return sb.toString();
    }
}