Problem Statement

You are given a string num representing a non-negative integer and an integer k.

• Remove exactly k digits from the number so that the resulting number is the smallest possible.
• Return the resulting number as a string.
• Leading zeros should be removed. If the resulting number is empty, return "0".

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove digits 4, 3, and 2 → smallest number is 1219

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove leading 1 → smallest number is 200

---

Approach to Solve the Problem (Stack-based Greedy)

Idea:

• To get the smallest number, remove digits from left to right if the current digit is larger than the next digit.
• Use a stack to maintain the digits of the smallest number.

Steps:

1. Initialize an empty stack to store digits.
2. Traverse the string num:
   • While k > 0, stack is not empty, and top of stack > current digit:
     • Pop the stack (remove a larger digit to make number smaller)
     • Decrement k
   • Push the current digit to the stack
3. After traversal:
   • If k > 0, remove remaining digits from the end of the number (stack).
4. Build the resulting number from the stack.
5. Remove leading zeros.
6. If result is empty, return "0".

Why this works (Greedy):

• Always remove the first larger digit encountered before a smaller digit → guarantees minimal number.
• Using a stack helps track the sequence efficiently.

---

Java Code Solution

import java.util.*;

public class RemoveKDigits {

    public static String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char digit : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peekLast() > digit) {
                stack.pollLast();
                k--;
            }
            stack.addLast(digit);
        }

        // Remove remaining digits from the end
        while (k > 0 && !stack.isEmpty()) {
            stack.pollLast();
            k--;
        }

        // Build the resulting number
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pollFirst());
        }

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

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

    public static void main(String[] args) {
        String num = "1432219";
        int k = 3;
        String result = removeKdigits(num, k);
        System.out.println("Smallest number: " + result); // Output: 1219
    }
}

---

Dry Run Example

Input:

num = "1432219", k = 3

Step-by-step Execution:

1. Traverse digits:

• Digit ‘1’: stack empty → push ‘1’ → stack = [1]
• Digit ‘4’: top=1 < 4 → push ‘4’ → stack = [1,4]
• Digit ‘3’: top=4 > 3 → pop 4, k=2 → push 3 → stack = [1,3]
• Digit ‘2’: top=3 > 2 → pop 3, k=1 → push 2 → stack = [1,2]
• Digit ‘2’: top=2 <= 2 → push 2 → stack = [1,2,2]
• Digit ‘1’: top=2 > 1 → pop 2, k=0 → push 1 → stack = [1,2,1]
• Digit ‘9’: push 9 → stack = [1,2,1,9]

2. k=0 → no more removals needed.
3. Build result → "1219"
4. Remove leading zeros → none → result = "1219"

---

Textual Diagram for Understanding

num: 1 4 3 2 2 1 9
k=3

Stack evolution:
[1] → push 1
[1,4] → push 4
[1,3] → pop 4, push 3
[1,2] → pop 3, push 2
[1,2,2] → push 2
[1,2,1] → pop 2, push 1
[1,2,1,9] → push 9

Final number: 1219

---

Complexity Analysis

• Time Complexity: O(n)
  • Each digit is pushed and popped at most once.
• Space Complexity: O(n)
  • Stack stores digits of the resulting number.