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();
        
        //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 
    HashSet S = 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