Introduction
The "Remove K Digits" problem is a classic greedy algorithm and monotonic stack interview question. Given a number represented as a string and an integer k, the goal is to remove exactly k digits so that the resulting number is as small as possible.
The relative order of the remaining digits must remain unchanged. Additionally, the final result should not contain leading zeros, and if all digits are removed, the function should return "0".
This problem demonstrates how a greedy strategy combined with a stack-like data structure can efficiently produce the optimal answer in linear time.
Problem Summary
Given:
Remove exactly k digits such that:
The resulting number is the smallest possible.
The relative order of the remaining digits remains unchanged.
The result does not contain leading zeros.
If all digits are removed, return "0".
Key Idea
The optimal solution uses a greedy strategy with a stack-like structure.
The intuition is:
Smaller digits should appear earlier in the result.
If a larger digit appears before a smaller digit, removing the larger digit helps minimize the final number.
We maintain a monotonic increasing sequence of digits.
Whenever a smaller digit arrives, we remove larger digits from the end of the current result as long as removals are still available.
Why the Greedy Approach Works
Consider the number:
1432219
Suppose we can remove digits.
When we encounter:
4 followed by 3
keeping 4 before 3 makes the number larger.
Removing 4 produces:
132219
which is smaller.
This observation leads to the greedy rule:
Whenever a larger digit appears before a smaller digit, remove the larger digit if removals are still available.
Approach Explained
We iterate through each digit in the string.
Step 1: Maintain a Stack-Like Structure
Use a StringBuilder as a stack to store digits.
Step 2: Remove Larger Previous Digits
While:
remove the last digit.
This helps create the smallest possible prefix.
Step 3: Add Current Digit
Append the current digit to the stack.
Step 4: Remove Remaining Digits
After processing all digits, there may still be removals left.
If:
k > 0
remove digits from the end of the stack.
Step 5: Remove Leading Zeros
Skip all leading zeros in the final result.
Step 6: Handle Empty Result
If the resulting string becomes empty, return:
"0"
Example Walkthrough
Input
s = "1432219"
k = 3
Processing
Read 1
Stack: 1
Read 4
Stack: 14
Read 3
Remove 4 because:
4 > 3
Stack:
13
Remaining removals:
k = 2
Read 2
Remove 3.
Stack:
12
Remaining removals:
k = 1
Read 2
Stack: 122
Read 1
Remove last 2.
Stack:
121
Remaining removals:
k = 0
Continue processing remaining digits.
Final result:
1219
Java Implementation
class Solution {
public String removeKdig(String s, int k) {
StringBuilder stack = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
while (k > 0 && stack.length() > 0 &&
stack.charAt(stack.length() - 1) > ch) {
stack.deleteCharAt(stack.length() - 1);
k--;
}
stack.append(ch);
}
while (k > 0 && stack.length() > 0) {
stack.deleteCharAt(stack.length() - 1);
k--;
}
int i = 0;
while (i < stack.length() && stack.charAt(i) == '0') {
i++;
}
String result = stack.substring(i);
return result.length() == 0 ? "0" : result;
}
}
Handling Leading Zeros
Consider:
s = "10200"
k = 1
After removing 1:
0200
Leading zeros should not appear in the answer.
After trimming:
200
Final output:
"200"
Edge Cases
All Digits Removed
Input:
s = "10"
k = 2
Output:
"0"
Already Increasing Number
Input:
s = "12345"
k = 2
No beneficial removals occur during traversal.
Remove from the end:
123
Number With Leading Zeros After Removal
Input:
s = "10020"
k = 1
Output:
"20"
Complexity Analysis
Time Complexity
O(n)
Each digit is:
Therefore, every character is processed at most twice.
Space Complexity
O(n)
The stack-like structure stores up to n digits.
Why This Solution Is Optimal
The algorithm follows a greedy strategy:
Always remove larger digits that appear before smaller digits.
Build the smallest possible prefix at every step.
Preserve the relative order of remaining digits.
The monotonic increasing structure ensures that every decision contributes to minimizing the final number.
Because each digit is pushed and popped at most once, the solution achieves optimal linear performance.
Conclusion
The Remove K Digits problem is a classic example of combining a greedy strategy with a monotonic stack. By removing larger digits whenever a smaller digit appears later, we ensure that smaller digits occupy more significant positions in the final number.
After processing all digits, any remaining removals are applied from the end, and leading zeros are removed to produce the final answer.
This approach provides an efficient solution with:
Time Complexity : O(n)
Space Complexity : O(n)
making it suitable even for very large input strings.