Dare2Solve
Given a non-negative integer num
represented as a string, and an integer k
, remove k
digits from the number so that the resulting number is the smallest possible. The result should not contain leading zeros unless the result is exactly "0".
The problem can be thought of as selecting digits in a greedy manner to form the smallest possible number. At each step, we aim to remove digits that make the number larger. For example, we prefer smaller digits earlier in the number as they contribute to a smaller overall value.
k
) to remove.k > 0
), pop the remaining digits from the stack.O(n)
, where n
is the length of the input number string. Each digit is pushed and popped from the stack at most once.
O(n)
, for the stack to store the digits.
class Solution {
public:
string removeKdigits(string num, int k) {
vector<char> stack;
for (char d : num) {
while (!stack.empty() && k > 0 && stack.back() > d) {
stack.pop_back();
k--;
}
stack.push_back(d);
}
while (k > 0) {
stack.pop_back();
k--;
}
string result = "";
for (char c : stack) {
if (!(result.empty() && c == '0')) {
result.push_back(c);
}
}
return result.empty() ? "0" : result;
}
};
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack = []
for d in num:
while stack and k > 0 and stack[-1] > d:
stack.pop()
k -= 1
stack.append(d)
while k > 0:
stack.pop()
k -= 1
# Remove leading zeros
result = ''.join(stack).lstrip('0')
return result if result else '0'
class Solution {
public String removeKdigits(String num, int k) {
StringBuilder stack = new StringBuilder();
for (char d : num.toCharArray()) {
while (stack.length() > 0 && k > 0 && stack.charAt(stack.length() - 1) > d) {
stack.deleteCharAt(stack.length() - 1);
k--;
}
stack.append(d);
}
while (k > 0) {
stack.deleteCharAt(stack.length() - 1);
k--;
}
while (stack.length() > 0 && stack.charAt(0) == '0') {
stack.deleteCharAt(0);
}
return stack.length() == 0 ? "0" : stack.toString();
}
}
var removeKdigits = function (num, k) {
const stack = [];
for (let d of num) {
while (stack.length > 0 && k > 0 && stack[stack.length - 1] > d) {
stack.pop();
k--;
}
stack.push(d);
}
while (k > 0) {
stack.pop();
k--;
}
while (stack.length > 0 && stack[0] == '0') {
stack.shift()
}
return stack.length === 0 ? '0' : stack.join('');
};