# Solution For Remove K Digits

Problem Statement:

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Example:

Input: num = “1432219”, k = 3

Output: “1219”

Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest possible.

Solution:

The main idea here is to keep the digits that are smaller than their right neighbor. If there are no such digits, then we can simply remove the last digit, as the rightmost digit would be the largest. If k is not reduced to zero yet, we can repeat the same process again. However, in order to reduce the number of iterations, we can use a stack to keep track of the digits we have considered so far.

Algorithm:

- Create an empty stack to keep track of the digits.
- Loop through each digit in the num string.
- While the stack is not empty and k > 0 and the top of the stack is greater than the current digit, pop the top element from the stack and decrease k.
- Add the current digit to the stack.

- If k is not zero, pop the top elements of the stack until k becomes zero.
- If the stack is empty, return zero, otherwise return the digits in the stack as a string.

Python Code:

class Solution:

def removeKdigits(self, num: str, k: int) -> str:

digits = [] # create a stack to keep track of digits

for digit in num:

# while the stack is not empty, k is greater than 0, and the top of the stack is larger than the current digit

while len(digits) > 0 and k > 0 and digits[-1] > digit:

digits.pop() # remove the top element from the stack

k -= 1 # decrease k

digits.append(digit) # add the current digit to the stack

```
# if k is still not zero, we need to remove the remaining digits from the end of the stack
while k > 0 and len(digits) > 0:
digits.pop()
k -= 1
# if the stack is empty, return zero
if len(digits) == 0:
return "0"
# otherwise, return the digits in the stack as a string
return str(int("".join(digits)))
```

## Step by Step Implementation For Remove K Digits

class Solution { public String removeKdigits(String num, int k) { //edge case if(num.length() == k){ return "0"; } //use a stack to keep track of the digits in the new number Stackstack = new Stack<>(); for(int i = 0; i < num.length(); i++){ //while the stack is not empty and the current digit is less than the top of the stack //and we still have digits to remove while(!stack.isEmpty() && stack.peek() > num.charAt(i) && k > 0){ //pop off the top of the stack stack.pop(); //decrement k k--; } //push the current digit onto the stack stack.push(num.charAt(i)); } //while we still have digits to remove while(k > 0){ //pop off the top of the stack stack.pop(); //decrement k k--; } //build up the new number StringBuilder newNum = new StringBuilder(); while(!stack.isEmpty()){ newNum.append(stack.pop()); } //reverse the new number newNum.reverse(); //remove any leading 0's while(newNum.length() > 1 && newNum.charAt(0) == '0'){ newNum.deleteCharAt(0); } return newNum.toString(); } }

class Solution: def removeKdigits(self, num: str, k: int) -> str: # Base case if k == 0: return num if k == len(num): return "0" # Use stack to keep track of the digits in the resulting number stack = [] # Iterate through the digits in the number for digit in num: # As long as there are more digits to remove # and the digit we are looking at is larger than # the digit at the top of the stack, we remove # the top digit from the stack while k > 0 and stack and stack[-1] > digit: stack.pop() k -= 1 # Add the current digit to the stack stack.append(digit) # Remove the remaining digits from the end of the stack while k > 0: stack.pop() k -= 1 # Build the resulting number and handle the case # where the resulting number starts with a zero result = "".join(stack).lstrip("0") return result if result else "0"

var removeKdigits = function(num, k) { // your code here };

One possible solution is to use a stack to keep track of the digits in the number. Start by pushing the first digit onto the stack. For each subsequent digit, compare it to the top of the stack. If it is less than or equal to the top of the stack, then push it onto the stack. If it is greater than the top of the stack, then pop the top of the stack off and continue comparing the current digit to the new top of the stack. Repeat this process until either the stack is empty or you have reached the end of the number. If there are still digits remaining in the number after the stack is empty, then those digits are the ones that should be removed.

using System; class GFG { // Function to calculate the // length of the longest // subsequence of consecutive // digits static int findLongestConseqSubseq(int[] arr, int n) { // Hash all array elements HashSetS = new HashSet (); for (int i = 0; i < n; ++i) S.Add(arr[i]); // check each possible sequence // from the start then update // optimal length int ans = 0; // Traverse through array elements // and count all possible sequences for (int i = 0; i < n; ++i) { // if current element is the // starting element of a sequence if (!S.Contains(arr[i] - 1)) { // Then check for next elements // in the sequence int j = arr[i]; while (S.Contains(j)) j++; // update optimal length if // this length is more if (ans < j - arr[i]) ans = j - arr[i]; } } return ans; } // Driver code public static void Main() { int[] arr = { 1, 9, 3, 10, 4, 20, 2 }; int n = arr.Length; Console.Write("Length of the Longest " + "consecutive subsequence is " + findLongestConseqSubseq(arr, n)); } } // This code is contributed by 29AjayKumar