Leetcode
Youtube
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) {
if(num.length()==k) {
return "0";
}
int top = 0;
char[] ca = new char[num.length()];
for(char c: num.toCharArray()){
while(k>0 && top>0 && ca[top-1]>c){
top--;
k--;
}
ca[top++] = c;
}
int i = 0, len = top-k;
while(i < len-1 && ca[i] == '0') {
i++;
}
return String.valueOf(ca, i, len-i);
}
}class Solution:
def removeKdigits(self, num: str, k: int) -> str:
if k == len(num):
return '0'
top = 0
arr = ['']*len(num)
for c in num:
while k>0 and top>0 and arr[top-1] > c:
top -= 1
k -= 1
arr[top] = c
top += 1
i = 0
while i < top-k-1 and arr[i] == '0':
i += 1
return ''.join(arr[i:top-k])