Java Solution using Stack with O(N) runtime


  • 0
    L

    The below code is my solution to this problem just using stack and hard code condition cases.

    public class Solution {

    public String removeKdigits(String num, int k) {

        if (num.length() == k) {
            return "0";
        }
        
        Stack<Character> stack = new Stack<Character>();
        int index = 1;
        stack.push(num.charAt(0));
        
        while (index < num.length() && k > 0) {
            if (stack.isEmpty()) {
                if (num.charAt(index) == '0') {
                    index++;
                } else {
                    stack.push(num.charAt(index++));
                }
            } else {
                if (num.charAt(index) < stack.peek()) {
                    stack.pop();
                    k--;
                } else if (index == num.length() - 1) {
                    index++;
                    k--;
                } else {
                    stack.push(num.charAt(index++));
                }
            }
        }
        
        while (stack.size() > 0 && k > 0) {
            stack.pop();
            k--;
        }
        
        StringBuilder sb = new StringBuilder();
        if (stack.size() == 0) {
            while (index < num.length() && num.charAt(index) == '0') {
                index++;
            }
        }
        while (stack.size() > 0) {
            sb.insert(0, stack.pop());
        }
        sb.append(num.substring(index));
        return sb.length() == 0? "0" : sb.toString();
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.