Greedy Strings: String Reconstruction and Removal

This module covers three classic "Monotonic Stack + Greedy" problems. Their core logic is nearly identical: as we traverse the sequence, we use a stack to maintain the best current candidate, popping the top whenever the "next" element provides a better lexicographical or numerical position.

1. Remove Duplicate Letters (LeetCode 316)

Problem Description

Given a string s, remove duplicate letters so that every letter appears once and only once. You must ensure that the result is the smallest in lexicographical order among all possible results.

Example: s = "bcabc" $\to$ "abc"; s = "cbacdcbc" $\to$ "acdb".

Greedy Insight

As we iterate through the characters c:

• If c is already in our candidate stack, we skip it.
• If not, we look at the character at the top of our stack: if stackTop > c AND stackTop appears later in the string (we have another chance to pick it), we pop stackTop.
• This ensures we keep the stack sorted as much as possible without losing any unique letters.

public String removeDuplicateLetters(String s) {
    int[] count = new int[26];          // Frequency of remaining characters
    boolean[] inStack = new boolean[26]; // Whether char is already in the stack
    for (char c : s.toCharArray()) count[c - 'a']++;

    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        count[c - 'a']--; // One less of this character available in the remainder
        if (inStack[c - 'a']) continue;

        // While top is larger than current and top appears later, pop it
        while (!stack.isEmpty() && stack.peek() > c && count[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();
}

2. Remove K Digits (LeetCode 402)

Problem Description

Given a non-negative integer represented as a string num and an integer k, remove k digits from the number so that the remaining number is the smallest possible.

Example: num = "1432219", k = 3 $\to$ "1219".

Greedy Insight

High-place digits (leftmost) have far more weight than low-place digits. If a digit is larger than its immediate successor, removing it will result in a smaller overall number.

We use a monotonic increasing stack:

• If stackTop > currentDigit and we still have removals left (k > 0), pop the stack.
• After the traversal, if k is still positive, remove digits from the end (since the stack is now sorted).

public String removeKdigits(String num, int k) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char d : num.toCharArray()) {
        while (k > 0 && !stack.isEmpty() && stack.peek() > d) {
            stack.pop();
            k--;
        }
        stack.push(d);
    }

    // Remainder k: pop from the tail
    while (k-- > 0) stack.pop();

    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) sb.append(stack.pollLast());

    // Clean leading zeros
    while (sb.length() > 1 && sb.charAt(0) == '0') sb.deleteCharAt(0);

    return sb.length() == 0 ? "0" : sb.toString();
}

3. Create Maximum Number (LeetCode 321)

Problem Description

Given two arrays nums1 and nums2 of lengths $m$ and $n$, select $k$ digits (maintaining relative order within their source array) to create the maximum possible merged number.

Example: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5 $\to$ [9,8,6,5,3].

Strategy: Task Decomposition

1. Enumerate Allocation: Pick $k_1$ from nums1 and $k_2 = k - k1$ from nums2.
2. Monotonic Stack Selection: For a single array, find the maximum subsequence of a specific size (using a monotonic decreasing stack).
3. Optimized Merge: Combine two maximum subsequences into the overall maximum.

public int[] maxNumber(int[] nums1, int[] nums2, int k) {
    int m = nums1.length, n = nums2.length;
    int[] best = new int[k];

    for (int k1 = Math.max(0, k - n); k1 <= Math.min(k, m); k1++) {
        int[] sub1 = maxSubsequence(nums1, k1);
        int[] sub2 = maxSubsequence(nums2, k - k1);
        int[] candidate = merge(sub1, sub2);
        if (compare(candidate, 0, best, 0) > 0) best = candidate;
    }
    return best;
}

private int[] maxSubsequence(int[] nums, int size) {
    int[] stack = new int[size];
    int top = 0, drop = nums.length - size;
    for (int num : nums) {
        while (drop > 0 && top > 0 && stack[top - 1] < num) {
            top--;
            drop--;
        }
        if (top < size) stack[top++] = num;
        else drop--;
    }
    return stack;
}

private int[] merge(int[] a, int[] b) {
    int[] res = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length || j < b.length) {
        res[k++] = compare(a, i, b, j) >= 0 ? a[i++] : b[j++];
    }
    return res;
}

private int compare(int[] a, int i, int[] b, int j) {
    while (i < a.length && j < b.length) {
        if (a[i] != b[j]) return a[i] - b[j];
        i++; j++;
    }
    return (a.length - i) - (b.length - j);
}

Summary Summary Table

[!TIP] Universal Pattern: Iterate once, maintain a stack. Whenever the current element is "better" than the top and you have the "budget" to replace it, pop the top. 筋