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);

        // Remove leading 0s
        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);
    }
}