The challenge
Remove exactly k digits from a decimal string to produce the smallest possible number as a string.
Nonempty decimal string without leading zeros except 0 itself. 0 ≤ k ≤ n. Normalize leading zeros and return 0 if empty.
Example
1432219, k = 3 → 1219.
Use the walkthrough below to inspect the input and each state change.
See Remove K Digits, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyk = 3
- Current input index
- —
- Main stack size
- 0
Step 01 / 12
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: ["1","4","3","2","2","1","9"] · k = 3
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
While deletions remain and top > current, remove the top digit.
Indices are zero-based. C++ uses C++17 or later.
def solve(values, k):
stack = []
for digit in values:
while k and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
if k: del stack[-k:]
return ''.join(stack).lstrip('0') or '0'
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
string solve(const vector<string>& values, int k) {
string stack;
for (const auto& token : values) {
char digit = token[0];
while (k > 0 && !stack.empty() && stack.back() > digit) {
stack.pop_back(); --k;
}
stack += digit;
}
stack.resize(stack.size() - k);
auto first = stack.find_first_not_of('0');
return first == string::npos ? "0" : stack.substr(first);
}