package advanced.greedy.lc402_removekdigits;

import java.util.Stack;

/**
 * Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
 */
public class Solution {

    // 1AC. Greedy O(N) time and space.
    public String removeKdigits(String num, int k) {
        if (num.isEmpty() || num.length() <= k) return "0";
        Stack<Character> s = new Stack<>();
        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);
            for (; !s.isEmpty() && k > 0 && s.peek() > c; k--) {
                s.pop();
            }
            s.push(c);
        }

        // Remove leading zero by iterating stack from bottom (note k > 0 case)
        StringBuilder ret = new StringBuilder();
        for (Character c : s) {
            if (c == '0' && ret.length() == 0) continue;
            else ret.append(c);
        }
        return ret.length() == 0 ? "0" : ret.substring(0, ret.length() - k);
    }

    public String removeKdigits_my(String num, int k) {
        Stack<Character> s = new Stack<>();
        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);
            for (; !s.isEmpty() && k > 0 && s.peek() > c; k--) {
                s.pop();
            }
            s.push(c);
        }

        while (!s.isEmpty() && k-- > 0) { // eg.112, k=1
            s.pop();
        }

        StringBuilder ret = new StringBuilder();
        for (Character c : s) { // iterate from bottom
            if (c == '0' && ret.length() == 0) continue;
            else ret.append(c);
        }
        return ret.length() == 0 ? "0" : ret.toString();
    }

}

@@ -239,16 +239,766 @@
 tion %7B%0A%0A
+    // 2AC%0A    public String removeKdigits(String num, int k) %7B%0A        if (num.isEmpty() %7C%7C num.length() %3C= k) return %220%22;%0A        Stack%3CCharacter%3E s = new Stack%3C%3E();%0A        for (int i = 0; i %3C num.length(); i++) %7B%0A            char c = num.charAt(i);%0A            while (!s.isEmpty() && c %3C s.peek() && k %3E 0) %7B%0A                s.pop();%0A                k--;%0A            %7D%0A            s.push(c);%0A        %7D%0A%0A        // Remove leading zero by iterating stack from bottom (note k %3E 0 case)%0A        StringBuilder ret = new StringBuilder();%0A        for (char c : s) %7B%0A            if (c != '0' %7C%7C ret.length() %3E 0) %7B%0A                ret.append(c);%0A            %7D%0A        %7D%0A        return ret.length() == 0 ? %220%22 : ret.substring(0, ret.length() - k);%0A    %7D%0A%0A
     // 1
@@ -1052,32 +1052,33 @@
 ng removeKdigits
+1
 (String num, int

remove k digits