1209. Remove All Adjacent Duplicates in String II - Medium

前往題目

想法

• Stack

思路

1. 用Stack儲存每個字母和當前有幾個相鄰且相同的
2. 達到k就pop
3. 沒達到就計數+1然後繼續
4. 相鄰的不是同字母計數=1
5. 回傳結果

Code

看了Hint自己寫出來了，insert耗費資源，用append最後再reverse就好

class Solution {
    public String removeDuplicates(String s, int k) {
        // char -> count
        Stack<Pair<Character, Integer>> stack = new Stack();
        // Make stack non-empty, convenient for the algo.
        stack.push(new Pair('A', 0));

        for (char c : s.toCharArray()) {
            // Previous char and count
            char prev = stack.peek().getKey();
            int prevCount = stack.peek().getValue();

            // Previous char is the same as the current, reached k
            if (!stack.isEmpty() && prev == c && prevCount + 1 == k) {
                // Pop k - 1 times
                for (int i = 0; i < k - 1; ++i) {
                    if (stack.isEmpty())
                        break;
                    stack.pop();
                }
            } else if (!stack.isEmpty() && prev == c) { // Previous char is the same as current, haven't reached k
                stack.push(new Pair(c, prevCount + 1));
            } else { 
                stack.push(new Pair(c, 1));
            }
        }
        StringBuilder sb = new StringBuilder();
        while (stack.size() > 1) {
            sb.append(stack.pop().getKey());
        }
        sb.reverse();

        return sb.toString();
    }
}