Decode String · Asteroid Collision (LeetCode 394/735)

Decode String (LeetCode 394)

Input: k[encoded_string] $\rightarrow$ Repeat encoded_string exactly k times.

public String decodeString(String s) {
    Deque<Integer> countStack = new ArrayDeque<>();
    Deque<StringBuilder> strStack = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;
    
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            // Enter a new nested context: save current k and builder
            countStack.push(k); 
            k = 0;
            strStack.push(cur); 
            cur = new StringBuilder();
        } else if (c == ']') {
            // Exit nested context: repeat the current sub-string
            int repeatTimes = countStack.pop();
            StringBuilder previousText = strStack.pop();
            for (int i = 0; i < repeatTimes; i++) {
                previousText.append(cur);
            }
            cur = previousText; // Current becomes the merged result
        } else {
            cur.append(c);
        }
    }
    return cur.toString();
}

Asteroid Collision (LeetCode 735)

Positive numbers travel right, negative left. Collision only occurs if a right-moving asteroid meets a left-moving one.

public int[] asteroidCollision(int[] asteroids) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int a : asteroids) {
        boolean alive = true;
        // Collision if: current moves left (< 0) and stack top moves right (> 0)
        while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
            int top = stack.peek();
            if (top < -a) {
                stack.pop(); // Top asteroid explodes; check collision with next node
            } else if (top == -a) {
                stack.pop(); alive = false; // Both explode
            } else {
                alive = false; // Current asteroid explodes
            }
        }
        if (alive) stack.push(a);
    }
    
    int[] result = new int[stack.size()];
    for (int i = result.length - 1; i >= 0; i--) {
        result[i] = stack.pop();
    }
    return result;
}

Daily Temperatures (LeetCode 739)

Find the number of days to wait for a warmer temperature:

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // Monotonic decreasing, stores indices
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = i - idx;
        }
        stack.push(i);
    }
    return result;
}

Remove Duplicate Letters (LeetCode 316)

Remove duplicates to result in the lexicographically smallest string while maintaining original order and relative character counts.

public String removeDuplicateLetters(String s) {
    int[] freq = new int[26];
    boolean[] inStack = new boolean[26];
    for (char c : s.toCharArray()) freq[c - 'a']++;
    
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        freq[c - 'a']--; // Decrement availability
        if (inStack[c - 'a']) continue;
        
        // If top > current AND top appears later, pop top to improve lexicographical order
        while (!stack.isEmpty() && stack.peek() > c && freq[stack.peek() - 'a'] > 0) {
            inStack[stack.pop() - 'a'] = false;
        }
        stack.push(c);
        inStack[c - 'a'] = true;
    }
    
    StringBuilder sb = new StringBuilder();
    for (char c : stack) sb.append(c);
    return sb.reverse().toString();
}

Summary