Delete Digits

Source

LintCode 182 Delete Digits

Question

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

N <= 240 and k <= N

Solution

Java

public String DeleteDigits(String A, int k) {
    if (k <= 0 || A == null) return A;
    if (k == A.length()) return "";

    // The pattern is from left to right, remove the first kth number whose
    // next number is smaller than itself. e.g. 3407, k=2, we should remove 4 and 3
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < A.length(); i++) {
        Character c = A.charAt(i);
        while (!stack.isEmpty() && stack.peek() > c && k > 0) {
            stack.pop();
            k--;
        }
        stack.add(c);
    }

    // when finish one pass, it's possible that k is not 0 yet, that means
    // numbers are smaller than their next number
    while (k > 0) {
        stack.pop();
        k--;
    }

    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }

    // Remove 0s at the end, which are actually the highest order when we reverse the string
    while (sb.charAt(sb.length()-1) == '0') {
        sb.deleteCharAt(sb.length() - 1);
    }

    sb.reverse();
    return sb.toString();
}