LeetCode - 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.

입출력 예시

Example 1:

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

Example 2:

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

제약사항

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

Solution

[전략]
1. 알파벳별 마지막 index를 HashMap으로 관리
2. 각 알파벳을 순회하면서,
2.1스택이 비지 않은경우,

• 스택이 비거나, peek가 해당 알파벳의 마지막 index인 경우거나, peek 알파벳이 i번째 알파벳보다 작아질때까지 pop
  2.2 i번째 알파벳을 stack에 push

import java.util.*;

class Solution {
    public String removeDuplicateLetters(String s) {
        HashMap<Character, Integer> alphaHash = new HashMap<>();
        Set<Character> posAlphas = new HashSet<Character>();
        Stack<Character> stacks = new Stack<>();

        
        for (int i = 0; i < s.length(); i++) {
            // 알파벳별로 마지막 index를 저장
            alphaHash.put(s.charAt(i), i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            
            // 스택에 들어가있는 알파벳이면 패스
            // 스택에 들어가있다는 것은, stack peek에 해당 알파벳이 있거나, 해당 알파벳 이후 더 높은 알파벳들이 스택에 들어가있는 상태. 
            // 이 경우 뒤에 동일하게 나타나는 알파벳은 불필요함
            if (!posAlphas.contains(ch)) {
                // -> alphaHash.get(stacks.peek()) > i. i 이후에 동일 알파벳이 뒤에 남아있는지 확인
                while (!stacks.empty() && stacks.peek() > ch && alphaHash.get(stacks.peek()) > i) {
                    char peekCh = stacks.pop();
                    posAlphas.remove(peekCh);
                }
                stacks.push(ch);
                posAlphas.add(ch);
            }
        }

        for (Character c : stacks) {
            sb.append(c.charValue());
        }
        return String.valueOf(sb);
    }
}