# 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:

1. Create an empty stack to keep track of the digits.
2. 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.
3. If k is not zero, pop the top elements of the stack until k becomes zero.
4. 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
Stack stack = 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();

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) {
};```
```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
HashSet S = new HashSet();
for (int i = 0; i < n; ++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```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]