Smallest Value Achievable by Deleting K Digits
Solve this Problemnum represented as a string with no leading zeros, remove exactly k digits so that the digits left behind (in their original order) form the smallest possible number. Strip any leading zeros from the result, and return "0" if everything cancels out to zero (or nothing is left).
The greedy insight: reading left to right, a digit that is immediately followed by a strictly smaller digit should always be deleted — keeping it wastes a more significant place value on a bigger number than necessary, and the smaller digit that replaces it in that position can only help. Applying that rule with a stack, one pass, is exactly equivalent to repeatedly scanning for and removing the first such digit — the stack just recognizes the opportunity the instant it appears (an "aha, this new digit is smaller than what's on top") instead of rediscovering it with a fresh scan every time.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ num.length ≤ 12 - ◆
num consists only of digits '0'-'9', with no leading zeros - ◆
1 ≤ k ≤ num.length - ◆
If every digit ends up removed (or the result is all zeros), return "0"
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Repeatedly Remove the First Descending Digit
BruteRemoving one digit at a time, always pick the first digit (from the left) that is followed by a strictly smaller digit — deleting it can only help, since a bigger digit sitting before a smaller one is wasting a more significant place value. If no such digit exists (the number is non-decreasing throughout), remove the last digit instead. Repeat this single-removal process k times, rescanning from the beginning after every deletion, then strip any leading zeros left behind. Each of the k rescans costs O(n), giving O(n·k) total.
O(n·k)O(n)1class Solution {
2 public String removeKDigitsGreedy(String num, int k) {
3 StringBuilder sb = new StringBuilder(num);
4 for (int step = 0; step < k; step++) {
5 int i = 0;
6 while (i < sb.length() - 1 && sb.charAt(i) <= sb.charAt(i + 1)) {
7 i++;
8 }
9 sb.deleteCharAt(i);
10 }
11 int start = 0;
12 while (start < sb.length() - 1 && sb.charAt(start) == '0') start++;
13 String result = sb.substring(start);
14 return result.isEmpty() ? "0" : result;
15 }
16}Optimal — Single-Pass Monotonic Stack With a Removal Budget
OptimalProcess the digits left to right, keeping a stack that stays as non-decreasing as possible. Before pushing a new digit, pop off anything on top that's bigger than it — as long as there's still removal budget (k) left — since that's exactly "a bigger digit immediately followed by a smaller one," the same signal used in the brute force, just recognized the instant it appears instead of via a fresh rescan. If budget still remains after processing every digit (the number never had a descent), trim the excess from the end. Finally strip any leading zeros. Every digit is pushed once and popped at most once, giving O(n) total.
O(n)O(n)1class Solution {
2 public String removeKDigitsGreedy(String num, int k) {
3 Deque<Character> stack = new ArrayDeque<>();
4 for (char c : num.toCharArray()) {
5 while (k > 0 && !stack.isEmpty() && stack.peek() > c) {
6 stack.pop();
7 k--;
8 }
9 stack.push(c);
10 }
11 while (k > 0) {
12 stack.pop();
13 k--;
14 }
15 StringBuilder sb = new StringBuilder();
16 while (!stack.isEmpty()) sb.append(stack.pollLast());
17 int start = 0;
18 while (start < sb.length() - 1 && sb.charAt(start) == '0') start++;
19 String result = sb.substring(start);
20 return result.isEmpty() ? "0" : result;
21 }
22}