Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the resulting number is the smallest possible. The length of num is at most 10000 and k is such that 0 <= k <= num.length.
Constraints:
- 0 <= num.length <= 10000
- 0 <= k <= num.length
- num does not contain any leading zero
Examples:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the smallest possible number 1219
Solutions
Greedy, Stack
The idea is to iterate through the number from left to right and maintain a stack of digits. If the current digit is smaller than the top of the stack, we remove the top of the stack and decrement k until the stack is empty or the top of the stack is smaller than the current digit. Then we push the current digit to the stack. After iterating through the number, if k is still greater than 0, we remove the top of the stack k times. Finally, we remove any leading zeros from the stack and return the result as a string.
public String removeKdigits(String num, int k) {
StringBuilder sb = new StringBuilder();
for (char n : num.toCharArray()) {
while (k > 0 && sb.length() > 0 && sb.charAt(sb.length() - 1) > n) {
sb.deleteCharAt(sb.length() - 1);
k--;
}
sb.append(n);
}
while (k > 0) {
if (sb.length() > 0) {
sb.deleteCharAt(sb.length() - 1);
}
k--;
}
while (sb.length() > 1 && sb.charAt(0) == '0') {
sb.deleteCharAt(0);
}
return sb.length() == 0 ? "0" : sb.toString();
}Follow-up:
What if the input number is very large and cannot fit into memory?
