Best Digits

Category

Stacks

Difficulty

Medium

Problem Statement

Given a string representing a non-negative integer and an integer k, remove exactly k digits from the number to produce the largest possible remaining number. The relative order of the digits must be preserved. Return the result as a string.

Intuition

To maximize the resulting number, we want the leftmost digits to be as large as possible. When scanning left to right, if the current digit is larger than the previous digit, removing the previous (smaller) digit leads to a larger number. A stack-based greedy approach lets us efficiently decide which digits to remove: pop smaller digits from the stack when a larger digit arrives, as long as we still have removals left.

Approach

1. Initialize an empty stack and a counter for removals remaining (k).
2. Iterate through each digit in the string:
   • While the stack is not empty, the top of the stack is less than the current digit, and k > 0: pop from the stack and decrement k.
   • Push the current digit onto the stack.
3. If k > 0 after processing all digits, pop k elements from the top of the stack (remove trailing digits).
4. Join the stack contents into a string and return it.

Pseudocode

function bestDigits(number, numDigits):
    stack = []
    k = numDigits

    for digit in number:
        while stack is not empty and k > 0 and stack.top() < digit:
            stack.pop()
            k = k - 1
        stack.push(digit)

    // Remove remaining digits from the end if needed
    while k > 0:
        stack.pop()
        k = k - 1

    return join(stack, "")

Time & Space Complexity

• Time: O(n) where n is the number of digits. Each digit is pushed and popped at most once.
• Space: O(n) for the stack.

Key Insights

• This is a monotonic stack problem. The stack maintains digits in a way that maximizes the result.
• The greedy choice is to remove a smaller digit whenever a larger digit follows, as early removals have the biggest impact on the final number.
• If fewer than k removals happen during the iteration (e.g., digits are already in non-increasing order), the remaining removals are applied to the end.
• This is the inverse of the "remove k digits to get the smallest number" problem; instead of removing digits when a smaller one appears, we remove them when a larger one appears.

Edge Cases

• k = 0: return the original number unchanged.
• k = length(number) - 1: return the single largest digit.
• All digits are the same: remove any k digits; the result is n - k copies of that digit.
• Digits in non-increasing order: no removals happen during iteration; the last k digits are removed.
• Digits in strictly increasing order: the first k digits are removed.