💯Faster✅💯 Lesser✅Detailed Explaination🎯Stack🔥Greedy🧠Step-by-Step Explaination✅Python🐍Java🍵C+
\uD83D\uDE80 Hi, I\'m Mohammed Raziullah Ansari, and I\'m excited to share solution to this question with detailed explanation:\n\n# \uD83C\uDFAFProblem Explain
# \uD83D\uDE80 Hi, I\'m [Mohammed Raziullah Ansari](https://leetcode.com/Mohammed_Raziullah_Ansari/), and I\'m excited to share solution to this question with detailed explanation:\n\n# \uD83C\uDFAFProblem Explaination: \n- We have a string `num` representing non-negative integer and an integer `k`(k digits to remove from `num`).\n- We need to remove `k` digits from `num` such that it\'s the smallest possible integer after removing `k` digits from `num`.\n# \uD83E\uDDE0Thinking Behind the Solution:\n- If you see my approach or others\'s approaches to solutions for this problem, you will mostly find that most solutions use a greddy approach and stack to solve this problem. But why a greedy approach with a stack chosen for solving the "Remove K Digits" problem? The reason is:\n\n\n#### Greedy Approach:\n\n- The problem requires us to minimize the resulting number by removing k digits from the given number num.\n- A greedy approach is suitable because at each step (processing each digit), we make a locally optimal choice (keeping the smallest possible digit) with the aim of achieving the overall optimal solution (smallest resulting number).\n- By prioritizing smaller digits for the most significant places (leftmost positions), we ensure that the resulting number is minimized.\n\n#### Use of Stack:\n\n- A stack is employed to facilitate the greedy decision-making process:\n    - We traverse each digit of num and compare it with the top of the stack (the most recent digit we\'ve chosen to keep).\n    - If the current digit is smaller than the top of the stack and we still have removals (k > 0) remaining, we pop digits from the stack until a suitable position for the current digit is found.\n    - This stack-based approach allows us to maintain the order of digits while dynamically removing larger, less significant digits to form the smallest possible number.\n# \u2705Approach:\n- Initialize an empty stack.\n- Traverse each digit of num.\n    - For each digit, while the stack is not empty and k is greater than zero, check if the current digit is smaller than the top of the stack. If so, pop from the stack (remove the top digit) and decrement k.\n    - Push the current digit onto the stack.\n- After processing all digits, handle remaining k (if any) by popping from the stack.\n- Construct the resulting number from the stack and remove any leading zeros.\n- Return the smallest possible number as a string.\n\n# Let\'s walkthrough\uD83D\uDEB6\uD83C\uDFFB\u200D\u2642\uFE0F the implementation process with an example for better understanding\uD83C\uDFAF:\n\nLet\'s walk through the code step by step with the input `num = "1432219"` and `k = 3`.\n\n1. **Initial Values**:\n   - `k`: 3\n   - `stack`: []\n\n2. **Iteration 1 (`digit = \'1\'`)**:\n   - `digit`: \'1\'\n   - `k`: 3\n   - `stack`: [1]\n   \n3. **Iteration 2 (`digit = \'4\'`)**:\n   - `digit`: \'4\'\n   - `k`: 3\n   - `stack`: [1, 4]\n\n4. **Iteration 3 (`digit = \'3\'`)**:\n   - `digit`: \'3\'\n   - `k`: 2 (Remove \'4\' from stack because \'4\' > \'3\')\n   - `stack`: [1, 3] (Remove \'4\' from stack because \'4\' > \'3\')\n\n5. **Iteration 4 (`digit = \'2\'`)**:\n   - `digit`: \'2\'\n   - `k`: 1 (Remove \'3\' from stack because \'3\' > \'2\')\n   - `stack`: [1, 2] (Remove \'3\' from stack because \'3\' > \'2\')\n\n6. **Iteration 5 (`digit = \'2\'`)**:\n   - `digit`: \'2\'\n   - `k`: 1\n   - `stack`: [1, 2, 2] (No removal needed)\n\n7. **Iteration 6 (`digit = \'1\'`)**:\n   - `digit`: \'1\'\n   - `k`: 0 (Remove \'2\' from stack because \'2\' > \'1\')\n   - `stack`: [1, 2, 1] ( (Remove \'2\' from stack because \'2\' > \'1\')\n\n8. **Iteration 7 (`digit = \'9\'`)**:\n   - `digit`: \'9\'\n   - `k`: 0\n   - `stack`: [1, 2, 1, 9] \n\n### After Loop:\n   - `stack`: [1, 2, 1, 9]\n\n9. **Post-processing**:\n   - `stack = stack[:-k]` (Remove last `k` elements from `stack`): [1, 2, 1, 9]\n   - `\'\'.join(stack)`: \'1219\'\n   - `\'1219\'.lstrip(\'0\')`: \'1219\' (No leading zeros to strip)\n   - `result`: \'1219\'\n\n### Final Output:\nThe resulting smallest number after removing 3 digits from `num = "1432219"` is `\'1219\'`.\n\n# Code:\n```Python []\nclass Solution:\n    def removeKdigits(self, num: str, k: int) -> str:\n        stack = []\n        \n        for digit in num:\n            while stack and k > 0 and stack[-1] > digit:\n                stack.pop()\n                k -= 1\n            stack.append(digit)\n        \n        # If k > 0, remove remaining k digits from the end of the stack\n        stack = stack[:-k] if k > 0 else stack\n        \n        # Remove leading zeros\n        result = \'\'.join(stack).lstrip(\'0\')\n        \n        # Handle edge case where result might be empty\n        return result if result else \'0\'                \n```\n```Java []\nclass Solution {\n    public String removeKdigits(String num, int k) {\n        Stack<Character> stack = new Stack<>();\n        \n        for (char digit : num.toCharArray()) {\n            while (!stack.isEmpty() && k > 0 && stack.peek() > digit) {\n                stack.pop();\n                k--;\n            }\n            stack.push(digit);\n        }\n        \n        // Remove remaining k digits from the end of the stack\n        while (k > 0 && !stack.isEmpty()) {\n            stack.pop();\n            k--;\n        }\n        \n        // Construct the resulting string from the stack\n        StringBuilder sb = new StringBuilder();\n        while (!stack.isEmpty()) {\n            sb.append(stack.pop());\n        }\n        sb.reverse(); // Reverse to get the correct order\n        \n        // Remove leading zeros\n        while (sb.length() > 0 && sb.charAt(0) == \'0\') {\n            sb.deleteCharAt(0);\n        }\n        \n        // Handle edge case where result might be empty\n        return sb.length() > 0 ? sb.toString() : "0";\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    std::string removeKdigits(std::string num, int k) {\n        std::stack<char> stack;\n        \n        for (char digit : num) {\n            while (!stack.empty() && k > 0 && stack.top() > digit) {\n                stack.pop();\n                k--;\n            }\n            stack.push(digit);\n        }\n        \n        // Remove remaining k digits from the end of the stack\n        while (k > 0 && !stack.empty()) {\n            stack.pop();\n            k--;\n        }\n        \n        // Construct the resulting string from the stack\n        std::string result;\n        while (!stack.empty()) {\n            result += stack.top();\n            stack.pop();\n        }\n        std::reverse(result.begin(), result.end()); // Reverse to get the correct order\n        \n        // Remove leading zeros\n        size_t pos = result.find_first_not_of(\'0\');\n        result = (pos == std::string::npos) ? "0" : result.substr(pos);\n        \n        return result;\n    }\n};\n\n\n```\n\n\n\n\n\n\n\n\n\n
['String', 'Stack', 'Greedy', 'Monotonic Stack', 'C++', 'Java', 'Python3']