Python solution with explanation | Stack | Similar to problem 1673
The question asks us to remove k digits so that the resulting number is the smallest. Instead of approaching the problem with the mantality of removing k digits
The question asks us to remove k digits so that the resulting number is the smallest. Instead of approaching the problem with the mantality of removing k digits, think of the it from another perspective: if the len of the string is N, the question can be re-phrased as:\n\nFind the smallest number with length of N - k. \n\nThis is exactly the same as the problem [Find the Most Competitive Subsequence](https://leetcode.com/problems/find-the-most-competitive-subsequence/), with very minor changes. These 2 problems follow the exact same pattern, and the only way to recognize the pattern is, you guess it, do a lot of problems.\n\nHere are the solutions to both:\n\n**Find the most competitive subsequence**\n```\nresult = []\nfor i in range(len(nums)):\n\tcurr = nums[i]\n\twhile len(result) and result[-1] > curr and len(result) - 1 + len(nums) - i >= k:\n\t\tresult.pop()\n\tif len(result) < k:\n\t\tresult.append(curr)                \nreturn result\n```\n\n\n**Remove K digits**\n```\nif len(num) == k:\n\t\treturn "0"\nnumLen = len(num) - k\nresult = []\nfor i in range(len(num)):\n\tcurr = num[i]\n\twhile len(result) and result[-1] > curr and len(result) - 1 + len(num) - i >= numLen:\n\t\tresult.pop()\n\tif len(result) < numLen:\n\t\tresult.append(curr)\ni = 0\nfor i in range(len(result)):\n\tif result[i] != "0":\n\t\tbreak\nif i >= len(result):\n\treturn "0"\nreturn "".join(result[i:])\n```\n\nNotice that the for loop is exactly the same for both problems. The main idea here is: as long as we have enough digits to construct the subsequence (len(result) - 1 + len(nums) - i >= k), and the last number in the stack is greater than the current number (result[-1] > curr), we pop from the stack. After the while loop, if the len of the stack is less than the number of elements we need in the final result, we add the current number to the stack. I won\'t go into more details on how the core stack logic works as there are many great explanations in the discussion.\n\nFor this problem, after getting the resulting array, we need to perform one more step, which is to elimate the leading zeroes from the final result. And that is it!
['Stack', 'Python', 'Python3']