Given string num representing a non-negative integer num, and an integer k,
return the smallest possible integer after removing k digits from num.
Test Cases
Input:
(string) num = "1432219"
(int) k = 3
Output:
(string) "1219"
Explanation:
Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Input:
(string) num = "10200"
(int) k = 1
Output:
(string) "200"
Explanation:
Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Solution
class Solution {
public String removeKdigits(String num, int k) {
int n = num.length();
if (k == n) return "0";
Stack<Character> stack = new Stack<>();
for(int i=0; i<n; i++) {
while(k>0 && !stack.isEmpty() && stack.peek() > num.charAt(i)) {
stack.pop();
k--;
}
stack.push(num.charAt(i));
}
while(k>0) {
stack.pop();
k--;
}
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty())
sb.append(stack.pop());
sb.reverse();
while(sb.length()>1 && sb.charAt(0)=='0')
sb.deleteCharAt(0);
return sb.toString();
}
}class Solution:
def removeKdigits(self, num: str, k: int) -> str:
n = len(num)
if k == n: return "0"
stack = []
for i in range(n):
while k > 0 and stack and stack[-1] > num[i]:
stack.pop()
k-=1
stack.append(num[i])
while k > 0:
stack.pop()
k-=1
res = ""
while stack:
res = stack.pop() + res
return str(int(res))