Description
Given string num representing a non-negative integer num
, and an integer k
, return the smallest possible integer after removing k
digits from num
.
Examples:
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Solution in Python
Approach
- Monotonic Stack:
- Use a stack to keep track of digits of the resulting number in a way that the digits in the stack are in increasing order.
- When processing each digit, if the digit is smaller than the top of the stack and we still need to remove more digits (k>0), pop the stack.
- Remove Remaining Digits:
- After processing all digits in the input string, if k>0, remove the remaining k digits from the top of the stack.
- Construct the Result:
- Convert the stack to a string. Remove any leading zeros to ensure the output is a valid number. If the result is an empty string, return “0”.
- Constraints:
- Handle edge cases such as k=len(num) (all digits removed) or strings with leading zeros after removal.
Python
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
# Stack to store the digits of the resulting number
stack = []
# Step 1: Process each digit in the number
for digit in num:
# Remove digits from the stack if they are larger than the current digit
# and we still need to remove more digits (k > 0)
while stack and k > 0 and stack[-1] > digit:
stack.pop()
k -= 1
# Add the current digit to the stack
stack.append(digit)
# Step 2: If there are still digits to remove, remove them from the end of the stack
while k > 0:
stack.pop()
k -= 1
# Step 3: Construct the result by joining the stack
# Remove leading zeros by converting to an integer and back to a string
result = ''.join(stack).lstrip('0')
# If the result is empty, return "0"
return result if result else "0"
Detailed Explanation
- Building the Stack:
- As we iterate through the digits in
num
, we ensure that the stack remains monotonically increasing by popping elements that are greater than the current digit. This guarantees that the resulting number is minimized. - The condition
k > 0
ensures that we only remove digits while we are allowed to.
- As we iterate through the digits in
- Removing Excess Digits:
- If k>0 after processing all digits, we remove the remaining k digits from the top of the stack.
- Handling Leading Zeros:
- After constructing the number from the stack, use
.lstrip('0')
to remove any leading zeros. - If the resulting string is empty, return “0” as the smallest number.
- After constructing the number from the stack, use
- Edge Cases:
- If k=len(num), all digits are removed, and the result is “0”.
- If the input number has no digits after removal or is reduced to zeros, return “0”.
Solution in C++
C++
class Solution {
public:
string removeKdigits(string num, int k) {
// If k is equal to or greater than the size of the number, remove all digits
if (k >= num.size())
return "0";
// Stack to keep track of the smallest number
stack<char> st;
// Iterate over each digit in the input number
for (char digit : num) {
// Remove digits from the stack if the current digit is smaller than the top of the stack
// and we still need to remove more digits
while (!st.empty() && k > 0 && st.top() > digit) {
st.pop();
k--; // Decrease the count of digits to remove
}
// Push the current digit onto the stack
st.push(digit);
}
// If we still need to remove more digits (k > 0), remove them from the end of the stack
while (k > 0 && !st.empty()) {
st.pop();
k--;
}
// Build the resulting number from the stack
string result = "";
while (!st.empty()) {
result += st.top();
st.pop();
}
// The digits are in reverse order, so we need to reverse the string
reverse(result.begin(), result.end());
// Remove leading zeros, if any
int start = 0;
while (start < result.size() && result[start] == '0') {
start++;
}
// If the result is empty after removing leading zeros, return "0"
if (start == result.size())
return "0";
// Return the final result
return result.substr(start);
}
};
Solution in Javascript
JavaScript
var removeKdigits = function(num, k) {
// Edge case: If k is equal to the length of the number, return "0"
if (k === num.length) {
return "0";
}
// Initialize an empty stack to keep track of digits
const stack = [];
// Loop through each digit in the input string
for (let digit of num) {
// Remove digits from the stack while the following conditions are met:
// 1. There are still digits to remove (k > 0)
// 2. The current digit in the stack is greater than the current digit in the loop
while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
stack.pop(); // Remove the top digit from the stack
k--; // Decrease the count of digits to remove
}
// Push the current digit to the stack
stack.push(digit);
}
// If there are still digits left to remove (k > 0), remove them from the end of the stack
while (k > 0) {
stack.pop();
k--;
}
// Join the remaining digits in the stack to form the resulting number
// Use `replace` to remove leading zeros, if any
const result = stack.join('').replace(/^0+/, '');
// If the result is an empty string after removing leading zeros, return "0"
return result === '' ? "0" : result;
};
Solution in Java
Java
class Solution {
public String removeKdigits(String num, int k) {
// Edge case: If k is equal to the length of num, we remove all digits and return "0".
if (k == num.length()) {
return "0";
}
// Use a StringBuilder as a stack to store the digits of the resulting number.
StringBuilder stack = new StringBuilder();
// Iterate through each digit in the input string.
for (char digit : num.toCharArray()) {
// Remove the top digit from the stack if it's greater than the current digit
// and we still have digits left to remove (k > 0).
while (stack.length() > 0 && k > 0 && stack.charAt(stack.length() - 1) > digit) {
stack.deleteCharAt(stack.length() - 1); // Pop the top of the stack.
k--; // Decrement k as we've removed one digit.
}
// Append the current digit to the stack.
stack.append(digit);
}
// If there are still digits left to remove, remove them from the end of the stack.
while (k > 0 && stack.length() > 0) {
stack.deleteCharAt(stack.length() - 1);
k--;
}
// Remove any leading zeros from the stack.
while (stack.length() > 0 && stack.charAt(0) == '0') {
stack.deleteCharAt(0);
}
// If the stack is empty after processing, return "0".
if (stack.length() == 0) {
return "0";
}
// Convert the stack to a string and return it.
return stack.toString();
}
}