# LeetCode 402: Remove K Digits

## Problem Restatement

We are given a string `num` representing a non-negative integer and an integer `k`.

We must remove exactly `k` digits from `num`.

After removing those digits, the remaining digits must stay in their original relative order.

Return the smallest possible integer as a string.

The result should not contain leading zeroes. If all digits are removed, or the remaining number becomes empty after removing leading zeroes, return `"0"`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A numeric string `num` and an integer `k` |
| Output | The smallest possible number after removing exactly `k` digits |
| Constraint | Remaining digits must preserve original order |
| Important rule | Remove leading zeroes from the final answer |

Example function shape:

```python
def removeKdigits(num: str, k: int) -> str:
    ...
```

## Examples

For:

```python
num = "1432219"
k = 3
```

The answer is:

```python
"1219"
```

We remove `4`, `3`, and one `2`.

The remaining digits form the smallest possible number:

```python
1 2 1 9
```

Another example:

```python
num = "10200"
k = 1
```

The best digit to remove is `1`.

That leaves:

```python
"0200"
```

After removing leading zeroes, the result is:

```python
"200"
```

Another example:

```python
num = "10"
k = 2
```

We remove both digits.

Nothing remains, so the answer is:

```python
"0"
```

## First Thought: Brute Force

A brute force solution would try every way to remove `k` digits.

For each candidate result, we compare it with the best answer found so far.

This works for tiny inputs, but the number of ways to remove digits is large.

If `num` has length `n`, the number of possible choices is:

```python
C(n, k)
```

That becomes too large when `n` is up to `100000`.

We need a linear greedy method.

## Key Insight

For numbers with the same length, the leftmost digits matter the most.

For example:

```python
1299 < 1399
```

because the second digit `2` is smaller than `3`.

So when we scan from left to right, if we see a smaller digit after a larger digit, we should remove the larger digit if we still can.

Example:

```python
num = "143..."
```

When we see `3`, the previous digit is `4`.

Keeping `3` before the rest gives a smaller prefix than keeping `4`.

So we should remove `4`.

This suggests a monotonic stack.

We build the answer from left to right. While the last kept digit is larger than the current digit, we remove the last kept digit.

## Algorithm

Use a stack to store the digits we keep.

For each digit `d` in `num`:

1. While the stack is not empty, `k > 0`, and the top digit is greater than `d`, pop the stack.
2. Push `d` into the stack.
3. After processing all digits, if removals remain, remove digits from the end.
4. Join the stack into a string.
5. Remove leading zeroes.
6. Return `"0"` if the result is empty.

## Correctness

The algorithm removes a previous digit only when three conditions hold:

```python
k > 0
stack[-1] > current_digit
```

and the stack is non-empty.

This means a larger digit appears before a smaller digit. Removing the larger digit lets the smaller digit move into a more significant position. That strictly improves the number’s prefix.

The stack therefore keeps the smallest possible prefix after each processed digit, given the number of removals used so far.

If the input is already increasing, such as:

```python
"123456"
```

then no earlier digit is larger than a later digit. In that case, removing from the end is optimal because earlier digits are more significant and smaller.

After exactly `k` removals, the stack contains the best possible ordered subsequence of digits. Removing leading zeroes only changes the string representation, not the numeric value.

Therefore, the algorithm returns the smallest possible integer.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each digit is pushed once and popped at most once |
| Space | `O(n)` | The stack may store all digits |

## Implementation

```python
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []

        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1

            stack.append(digit)

        while k > 0 and stack:
            stack.pop()
            k -= 1

        result = "".join(stack).lstrip("0")

        return result if result else "0"
```

## Code Explanation

We start with an empty stack:

```python
stack = []
```

This stack stores the digits we currently plan to keep.

Then we scan each digit:

```python
for digit in num:
```

The main greedy step is:

```python
while k > 0 and stack and stack[-1] > digit:
    stack.pop()
    k -= 1
```

If the previous kept digit is larger than the current digit, removing it makes the number smaller. We can keep doing this while we still have removals left.

Then we keep the current digit:

```python
stack.append(digit)
```

After the scan, we may still have removals left. This happens when the digits are already increasing.

For example:

```python
num = "12345"
k = 2
```

The best result is:

```python
"123"
```

So we remove from the end:

```python
while k > 0 and stack:
    stack.pop()
    k -= 1
```

Then we build the result:

```python
result = "".join(stack).lstrip("0")
```

Finally:

```python
return result if result else "0"
```

This handles cases like `"10"` with `k = 2`, or `"10200"` with `k = 1`.

## Testing

```python
def test_remove_k_digits():
    s = Solution()

    assert s.removeKdigits("1432219", 3) == "1219"
    assert s.removeKdigits("10200", 1) == "200"
    assert s.removeKdigits("10", 2) == "0"
    assert s.removeKdigits("123456", 3) == "123"
    assert s.removeKdigits("100200", 1) == "200"
    assert s.removeKdigits("9", 1) == "0"
    assert s.removeKdigits("112", 1) == "11"

    print("all tests passed")
```

## Test Notes

| Test | Why |
|---|---|
| `"1432219"`, `k = 3` | Standard decreasing-then-mixed case |
| `"10200"`, `k = 1` | Checks leading zero removal |
| `"10"`, `k = 2` | Removes all digits |
| `"123456"`, `k = 3` | Increasing digits require removing from the end |
| `"100200"`, `k = 1` | Checks zero-heavy input |
| `"9"`, `k = 1` | Single digit removal |
| `"112"`, `k = 1` | Equal digits should not be popped unnecessarily |