Remove K Digits

`Greedy`, `Stack`, `String`

Medium

Given a non-negative integernumrepresented as a string, removekdigits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

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

Greedy + Recursion

29 ms, faster than 23.98%

``````class Solution {

public String removeKdigits(String num, int k) {
String result = helper(num, k);

int i = 0;
while (i < result.length() - 1) {
if (result.charAt(i) != '0') break;
i++;
}
result = result.substring(i, result.length());
if (result.length() == 0) {
return "0";
}
return result;
}

public String helper(String num, int k) {
if (num == null || k < 0 || num.length() <= k) {
return "";
}
if (k == 0) {
return num;
}

int m = num.length();
String candidate = num.substring(0, k + 1);
int minDigit = Integer.MAX_VALUE;
int index = 0;

for (int i = 0; i < candidate.length(); i++) {
int digit = candidate.charAt(i) - '0';
if (digit < minDigit) {
minDigit = digit;
index = i;
}
}
return candidate.substring(index, index + 1) + helper(num.substring(index + 1, m), k - index);
}
}
``````

Stack - Implementation 1

https://leetcode.com/problems/remove-k-digits/discuss/88708/Straightforward-Java-Solution-Using-Stack

``````public class Solution {
public String removeKdigits(String num, int k) {
int len = num.length();
//corner case
if(k==len)
return "0";

Stack<Character> stack = new Stack<>();
int i =0;
while(i<num.length()){
//whenever meet a digit which is less than the previous digit, discard the previous one
while(k>0 && !stack.isEmpty() && stack.peek()>num.charAt(i)){
stack.pop();
k--;
}
stack.push(num.charAt(i));
i++;
}

// corner case like "1111"
while(k>0){
stack.pop();
k--;
}

//construct the number from the stack
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty())
sb.append(stack.pop());
sb.reverse();

//remove all the 0 at the head
while(sb.length()>1 && sb.charAt(0)=='0')
sb.deleteCharAt(0);
return sb.toString();
}
}
``````

Stack- Implementation 2

https://leetcode.com/problems/remove-k-digits/discuss/88660/A-greedy-method-using-stack-O(n)-time-and-O(n)-space

``````public class Solution {
public String removeKdigits(String num, int k) {
int digits = num.length() - k;
char[] stk = new char[num.length()];
int top = 0;
// k keeps track of how many characters we can remove
// if the previous character in stk is larger than the current one
// then removing it will get a smaller number
// but we can only do so when k is larger than 0
for (int i = 0; i < num.length(); ++i) {
char c = num.charAt(i);
while (top > 0 && stk[top-1] > c && k > 0) {
top -= 1;
k -= 1;
}
stk[top++] = c;
}
// find the index of first non-zero digit
int idx = 0;
while (idx < digits && stk[idx] == '0') idx++;
return idx == digits? "0": new String(stk, idx, digits - idx);
}
}
``````