Sponsored
Sponsored
This approach uses a stack to build the smallest possible number. We iterate over each digit in the string, and for each digit, we compare it with the top of the stack (if the stack is not empty). If the current digit is smaller than the top of the stack and we still have digits to remove, we pop from the stack. Finally, after the loop, if there are remaining digits to remove, we simply remove them from the end of the constructed stack. This ensures the smallest possible arrangement of the remaining digits.
Time Complexity: O(n), where n is the number of digits in num, because each digit is processed at most twice (once pushed and once popped).
Space Complexity: O(n), because of the space required for the stack to hold the digits.
1#include <stdio.h>
2#include <string.h>
3
4char *removeKdigits(char *num, int k) {
5 int len = strlen(num);
6 // Resultant stack array
7 char *stack = (char *)malloc(len + 1);
8 int top = -1, toRemove = k;
9 for (int i = 0; i < len; i++) {
10 char c = num[i];
11 while (top >= 0 && stack[top] > c && toRemove > 0) {
12 top--;
13 toRemove--;
14 }
15 stack[++top] = c;
16 }
17 // The final size should be len - k
18 top = top - toRemove;
19 stack[top + 1] = '\0';
20 // Strip leading zeros
21 int offset = 0;
22 while (stack[offset] == '0') offset++;
23 // Check for the 'emptiness' of the string
24 if (offset > top) return "0";
25 return stack + offset;
26}This C implementation uses a dynamic array as a stack to manage the digits. The logic follows the same principle of keeping the smallest combination by popping larger top elements whenever a smaller element is encountered, provided there are removals left (k has not reached zero). Post-processing involves adjusting the size to 'remove' excess digits if not enough were popped, and leading zeros are stripped.