DSCPPAS272 - Editorial

editorial
,
1

Problem Statement:

Given a string num representing a non-negative integer and an integer k, the task is to remove k digits from num such that the resulting number is the smallest possible. The result should be returned as a string.

Approach:

The core idea of the solution is to use a greedy approach with a deque (double-ended queue) to maintain a sequence of digits that forms the smallest possible number after removing k digits. As we iterate through the digits of the input string, we ensure that each digit in the deque is smaller than or equal to the next digit, removing larger digits from the deque when they would lead to a larger number if left in place. After processing the entire string, if there are still digits left to remove, we remove them from the end of the deque. Finally, we remove any leading zeros from the deque and return the resulting smallest number as a string. This approach efficiently constructs the smallest possible number by making local optimal choices at each step.

Step-by-Step Explanation:

Step 1: Process the String Using a Deque

  • We iterate through each digit in the string num.
  • For each digit, we compare it with the last digit in the deque:
    • If the current digit is smaller than the last digit in the deque and we still have digits left to remove (k > 0), we remove the last digit from the deque.
    • This ensures that we discard larger digits that come before smaller digits, which helps in forming a smaller number.

Step 2: Handle Remaining Removals

  • If after processing the entire string, there are still digits left to remove (k > 0), we remove them from the end of the deque. This is because the remaining digits are the largest ones left, and removing them will yield a smaller number.

Step 3: Remove Leading Zeros

  • After constructing the number, there may be leading zeros. We remove these leading zeros from the deque.

Step 4: Convert Deque to String

  • Finally, we convert the deque into a string. If the deque is empty (which means the number has been reduced to 0), we return “0”.

Example:

Let’s consider the example where num = "1432219" and k = 3:

  1. Processing:
    • Start with an empty deque.
    • Add ‘1’ → deque: [1]
    • Compare ‘4’ with ‘1’ → add ‘4’ → deque: [1, 4]
    • Compare ‘3’ with ‘4’ → remove ‘4’, add ‘3’ → deque: [1, 3]
    • Compare ‘2’ with ‘3’ → remove ‘3’, add ‘2’ → deque: [1, 2]
    • Compare ‘2’ with ‘2’ → add ‘2’ → deque: [1, 2, 2]
    • Compare ‘1’ with ‘2’ → remove ‘2’, add ‘1’ → deque: [1, 2, 1]
    • Add ‘9’ → deque: [1, 2, 1, 9]
  2. Final Removals: We have removed 3 digits, so no further removals are needed.
  3. Result: Convert deque to string and remove leading zeros: “1219”.

The final answer is "1219".

Complexity:

  • Time Complexity: The solution runs in O(N) time, where N is the length of the string num, as each digit is processed at most twice (once pushed, possibly once popped).
  • Space Complexity: The space complexity is O(N) due to the space used by the deque.