package _402;

class Solution {
    public String removeKdigits(String num, int k) {
        if (k <= 0)
            return num;
        int len = num.length();
        StringBuilder res = new StringBuilder(len);
        return removeKdigitsIter(num, len - k, -1, res);
    }

    /**
     * @param left Number of the digits left
     * @param head The head index of current sub string
     * @param res  Temp sb to build result
     */
    private String removeKdigitsIter(String num, int left, int head, StringBuilder res) {
        if (left <= 0)
            return res.length() == 0 ? "0" : res.toString();
        head++;
        char min = num.charAt(head);
        int tail = num.length() - left + 1;
        for (int i = head; i < tail; i++) {
            if (num.charAt(i) < min) {
                min = num.charAt(i);
                head = i;
            }
        }
        boolean notLeading0 = res.length() != 0 || min != '0';
        if (notLeading0)
            res.append(min);
        return removeKdigitsIter(num, left - 1, head, res);
    }

    private static void testRemoveKdigits(String num, int k) {
        Solution solution = new Solution();
        System.out.println(solution.removeKdigits(num, k));
    }

    public static void main(String[] args) {
        testRemoveKdigits("4325643", 0);
    }
}