Remove K Digits

Problem Statement

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

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.

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public String removeKdigits(String num, int k) {
        
        Stack<Character> stack = new Stack<>();

        for(char digit : num.toCharArray()) {
            while(!stack.isEmpty() && k > 0 && stack.peek() > digit) {
                stack.pop();
                k -= 1;
            }
            stack.push(digit);
        }

        while(!stack.isEmpty() && k > 0) {
            stack.pop();
            k -= 1;
        }

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

        StringBuilder reversedString = tempResult.reverse();
        System.out.println(reversedString);
        int start = -1;
        for(int i = 0; i < reversedString.length(); i++) {
            if(reversedString.charAt(i) != '0') {
                start = i;
                break;
            }
        }

        if(start == -1) {
            return "0";
        }

        return reversedString.substring(start);
    }
}

C++ Code

class Solution {
public:
    string removeKdigits(string num, int k) {
        stack<char> st;
        
        for (char digit : num) {
            while (!st.empty() && k > 0 && st.top() > digit) {
                st.pop();
                k--;
            }
            st.push(digit);
        }

        while (!st.empty() && k > 0) {
            st.pop();
            k--;
        }

        string tempResult = "";
        while (!st.empty()) {
            tempResult += st.top();
            st.pop();
        }

        reverse(tempResult.begin(), tempResult.end());
        
        int start = -1;
        for (int i = 0; i < tempResult.length(); i++) {
            if (tempResult[i] != '0') {
                start = i;
                break;
            }
        }

        if (start == -1) {
            return "0";
        }

        return tempResult.substr(start);
    }
};

Python Code

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        
        for digit in num:
            while stack and k > 0 and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        
        while stack and k > 0:
            stack.pop()
            k -= 1
        
        temp_result = ''.join(stack)
        
        start = -1
        for i in range(len(temp_result)):
            if temp_result[i] != '0':
                start = i
                break
        
        if start == -1:
            return '0'
        
        return temp_result[start:]

Complexity Analysis

Time Complexity: O(N)
Space Complexity: O(N)