# Remove K Digits
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-k-digits)
Canonical: https://scaleengineer.com/dsa/problems/remove-k-digits
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack, Monotonic Stack
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Samsung](https://scaleengineer.com/companies/samsung), [Snowflake](https://scaleengineer.com/companies/snowflake), [Zoho](https://scaleengineer.com/companies/zoho), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [josh technology](https://scaleengineer.com/companies/josh-technology), [Coupang](https://scaleengineer.com/companies/coupang), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Snap](https://scaleengineer.com/companies/snap), [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
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.

**Example 3:**

**Input:** num = "10", k = 2
**Output:** "0"
**Explanation:** Remove all the digits from the number and it is left with nothing which is 0.

**Constraints:**

* `1 <= k <= num.length <= 105`
* `num` consists of only digits.
* `num` does not have any leading zeros except for the zero itself.

# Approaches
## Brute Force with Recursion
This approach explores all possible ways to remove `k` digits from the number. It's equivalent to generating all subsequences of length `n-k` (where `n` is the length of the original number), converting them to numbers, and finding the minimum among them. This is done using recursion and backtracking to explore every valid combination of `n-k` digits.
**Time:** O(C(n, k) * n), where C(n, k) is the number of combinations 'n choose k'. This is because we generate C(n, n-k) = C(n, k) subsequences, and for each, we might perform a string comparison that takes O(n) time. The complexity is exponential. · **Space:** O(n), where n is the length of `num`. This space is used by the recursion stack and the `StringBuilder` to store the current path.
**Pros:** Guaranteed to find the correct, optimal solution as it checks every possibility.
**Cons:** Extremely inefficient due to its exponential time complexity.; Infeasible for the given constraints (`n` up to 10^5), will result in a 'Time Limit Exceeded' error on any non-trivial test case.
### Explanation
We can define a recursive helper function to generate all subsequences of length `n-k`. The function, say `generate(index, current_path)`, takes the starting index in the input string `num` and the subsequence built so far (`current_path`).

The base case for the recursion is when the length of `current_path` becomes `n-k`. At this point, we have a complete candidate number. We compare it with the smallest number found so far (stored in a global variable) and update the minimum if the new candidate is smaller.

In the recursive step, we iterate from the current `index` to the end of `num`. For each digit `num[i]`, we append it to `current_path` and make a recursive call `generate(i + 1, ...)`. After the call returns, we backtrack by removing the digit we just added to explore other possibilities.

This method is exhaustive and guarantees finding the correct answer, but its performance is very poor due to the massive number of possibilities (C(n, k) combinations), making it impractical for large inputs.

```java
class Solution {
    String minNumStr = "";

    public String removeKdigits(String num, int k) {
        int n = num.length();
        if (k == n) return "0";
        
        generateSubsequences(num, n - k, 0, new StringBuilder());

        // Remove leading zeros
        int i = 0;
        while (i < minNumStr.length() - 1 && minNumStr.charAt(i) == '0') {
            i++;
        }
        String result = minNumStr.substring(i);
        return result.isEmpty() ? "0" : result;
    }

    private void generateSubsequences(String num, int len, int start, StringBuilder current) {
        if (current.length() == len) {
            if (minNumStr.isEmpty() || current.toString().compareTo(minNumStr) < 0) {
                minNumStr = current.toString();
            }
            return;
        }

        // Pruning: if not enough characters left to form a valid subsequence
        if (num.length() - start < len - current.length()) {
            return;
        }

        for (int i = start; i < num.length(); i++) {
            current.append(num.charAt(i));
            generateSubsequences(num, len, i + 1, current);
            current.deleteCharAt(current.length() - 1); // Backtrack
        }
    }
}
```
### Algorithm
- This approach attempts to find the solution by generating all possible numbers that can be formed by removing `k` digits and then finding the minimum among them.
- This is equivalent to finding all subsequences of length `n-k`, where `n` is the length of the input string `num`.
- A recursive function can be used to generate these subsequences.
- The function, say `generate(startIndex, currentPath)`, would build a path of digits.
- The base case is when `currentPath` reaches the desired length (`n-k`). At this point, the generated number is compared with the global minimum found so far.
- In the recursive step, we iterate through the remaining digits of `num` from `startIndex`, append a digit to `currentPath`, and recurse.
- Backtracking is used to explore all possibilities.
- A pruning optimization can be added: if the number of remaining digits in `num` is not enough to form a full `n-k` length subsequence, we can stop that path of recursion early.

## Iterative Deletion
This approach improves upon brute force by using a more direct greedy strategy. Instead of trying all combinations, we remove one digit at a time, for a total of `k` times. In each of the `k` iterations, we intelligently find the single best digit to remove to make the resulting number as small as possible.
**Time:** O(k * n). The outer loop runs `k` times. Inside, we scan the string (length up to `n`), and `StringBuilder.deleteCharAt` can take O(n) time. This results in a quadratic time complexity in the worst case (`k` is proportional to `n`). · **Space:** O(n) to store the number in a `StringBuilder` which allows for efficient modifications.
**Pros:** Much faster than the brute-force approach.; The logic is relatively straightforward to understand.
**Cons:** The time complexity of O(k*n) is too slow for the given constraints, where `k` and `n` can be up to 10^5.; Repeatedly creating new strings or deleting characters from a `StringBuilder` in a loop is inefficient.
### Explanation
The core idea is to repeat the process of removing a single digit `k` times. In each step, which digit should we remove? To make the resulting number smallest, we should aim to remove a larger digit from a more significant (leftmost) position.

We can scan the number from left to right and remove the first digit that is a "peak"—that is, a digit `num[i]` which is greater than the following digit `num[i+1]`. For example, in "1432", the first peak is '4'. Removing it gives "132", which is smaller than removing any other digit. If the number's digits are in non-decreasing order, like "12345", there is no such peak. In this case, the best digit to remove is the last one (the largest), resulting in "1234".

We apply this logic `k` times. In each iteration, we find the one best digit to remove, remove it, and use the resulting smaller number for the next iteration. This is greedy because we make the locally optimal choice at each of the `k` steps.

```java
class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder sb = new StringBuilder(num);
        
        for (int i = 0; i < k; i++) {
            int j = 0;
            // Find the first peak from the left
            while (j < sb.length() - 1 && sb.charAt(j) <= sb.charAt(j + 1)) {
                j++;
            }
            // Remove the peak (or the last digit if no peak is found)
            sb.deleteCharAt(j);
        }
        
        // Remove leading zeros
        int i = 0;
        while (i < sb.length() - 1 && sb.charAt(i) == '0') {
            i++;
        }
        
        String result = sb.substring(i);
        return result.isEmpty() ? "0" : result;
    }
}
```
### Algorithm
- The algorithm runs in a loop `k` times.
- In each of the `k` iterations, we find and remove one digit.
- To find the best digit to remove, we scan the current number string from left to right.
- We look for the first digit `num[i]` that is greater than its right neighbor `num[i+1]`. This digit is a "peak".
- Removing this peak `num[i]` yields the smallest possible number after one removal, because we are making a change at the most significant position possible.
- If such a peak is found at index `i`, we remove the character at `i` and proceed to the next of the `k` iterations.
- If the loop finishes without finding a peak, it means the digits are in non-decreasing order (e.g., "12345"). In this case, to make the number smallest, we must remove the largest digit, which is the last one.
- After `k` removals, we handle any leading zeros and return the final string.

## Greedy Approach with Stack
This is the most efficient approach, solving the problem in a single pass. It uses a greedy strategy with a stack to build the smallest possible resulting number. The key idea is to maintain a monotonically increasing sequence of digits in our result. Whenever we encounter a digit that is smaller than the previous one, we know the previous digit is a "peak" that should be removed.
**Time:** O(n). Each digit is pushed onto the stack once. A digit can be popped at most once. Therefore, we iterate through the digits of `num` a constant number of times, leading to a linear time complexity. · **Space:** O(n). In the worst case (e.g., an already sorted number like "12345"), the stack can grow to the size of the input string `n`.
**Pros:** Optimal time complexity of O(n), making it very efficient for large inputs.; Solves the problem in a single pass over the input string.
**Cons:** The logic can be slightly less intuitive to grasp initially compared to the iterative deletion method.
### Explanation
This optimal solution processes the number in one pass. We use a stack to build up the result. The goal is to keep the digits in the stack as small as possible from left to right, forming a monotonically increasing sequence.

As we iterate through each digit of the input `num`, we compare it with the digit at the top of the stack. If the current digit is smaller than the stack's top element, and we still have removals (`k > 0`), it means the digit on the stack is a "peak" that we can remove to make the number smaller. We pop it from the stack and decrement `k`. We repeat this process until the stack is empty, `k` is zero, or the top of the stack is smaller than or equal to the current digit.

After this check, we push the current digit onto the stack. This ensures that for any digit we push, we have removed all preceding larger digits that we are allowed to.

After iterating through the entire input string, it's possible that `k > 0`. This occurs if the input number's digits were already in non-decreasing order (e.g., "12345"). In this case, the largest digits are at the end of our constructed sequence (top of the stack), so we simply remove the last `k` digits.

Finally, we build the string from the stack, remove leading zeros, and return the result.

```java
class Solution {
    public String removeKdigits(String num, int k) {
        int n = num.length();
        if (k >= n) return "0";

        StringBuilder sb = new StringBuilder(); // Using StringBuilder as a stack
        
        for (char c : num.toCharArray()) {
            // While stack is not empty, k > 0, and top of stack > current char
            while (sb.length() > 0 && k > 0 && sb.charAt(sb.length() - 1) > c) {
                sb.deleteCharAt(sb.length() - 1);
                k--;
            }
            sb.append(c);
        }
        
        // If k > 0, remove remaining digits from the end (for cases like "12345")
        sb.setLength(sb.length() - k);
        
        // Remove leading zeros
        int i = 0;
        while (i < sb.length() && sb.charAt(i) == '0') {
            i++;
        }
        
        String result = sb.substring(i);
        
        return result.isEmpty() ? "0" : result;
    }
}
```
### Algorithm
- We use a data structure that behaves like a stack, such as `java.util.Stack` or a `StringBuilder`.
- We iterate through each digit of the input string `num` from left to right.
- For each digit `d`:
  - We check the top of the stack. As long as the stack is not empty, we have removals left (`k > 0`), and the digit at the top of the stack is greater than the current digit `d`, we pop from the stack and decrement `k`. This step removes larger digits that appear before a smaller digit.
  - After the while loop, we push the current digit `d` onto the stack.
- After iterating through all digits of `num`, if `k` is still greater than 0, it means the digits in the stack are in a non-decreasing order (e.g., "12345"). To get the smallest number, we must remove the largest digits, which are now at the end (top) of our stack. So, we remove the last `k` digits.
- Finally, we construct the result string from the stack's contents, remove any leading zeros, and handle the edge case of an empty result (which should be "0").

# Solutions
### Java

```java
class Solution { public String removeKdigits ( String num , int k ) { StringBuilder stk = new StringBuilder (); for ( char c : num . toCharArray ()) { while ( k > 0 && stk . length () > 0 && stk . charAt ( stk . length () - 1 ) > c ) { stk . deleteCharAt ( stk . length () - 1 ); -- k ; } stk . append ( c ); } for (; k > 0 ; -- k ) { stk . deleteCharAt ( stk . length () - 1 ); } int i = 0 ; for (; i < stk . length () && stk . charAt ( i ) == '0' ; ++ i ) { } String ans = stk . substring ( i ); return "" . equals ( ans ) ? "0" : ans ; } }
```

### CPP

```cpp
class Solution { public: string removeKdigits ( string num , int k ) { string stk ; for ( char & c : num ) { while ( k && stk . size () && stk . back () > c ) { stk . pop_back (); -- k ; } stk += c ; } while ( k -- ) { stk . pop_back (); } int i = 0 ; for (; i < stk . size () && stk [ i ] == '0' ; ++ i ) { } string ans = stk . substr ( i ); return ans == "" ? "0" : ans ; } };
```

### Python

```python
class Solution : def removeKdigits ( self , num : str , k : int ) -> str : stk = [] remain = len ( num ) - k for c in num : while k and stk and stk [ - 1 ] > c : stk . pop () k -= 1 stk . append ( c ) return '' . join ( stk [: remain ]). lstrip ( '0' ) or '0'
```