402. Remove K Digits

Description

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Constraints

• 1 <= k <= num.length <= 105

• num consists of only digits.

• num does not have any leading zeros except for the zero itself.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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.

Example 2

Example 3

Solutions

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */

class Solution {
    public String removeKdigits(String num, int k) {
        if(num == null || num.isBlank() || k > num.length()) {
            throw new IllegalArgumentException("Invalid parameters");
        }
        
        if(num.length() == k) {
            return "0";
        }
        
        int n = num.length();
        Deque<Character> stack = new ArrayDeque();
        
        for(int i = 0; i < n; i++) {
            char ch = num.charAt(i);
            while(k > 0 && !stack.isEmpty() && stack.peek() > ch) {
                stack.pop();
                k--;
            }
            stack.push(ch);
        }
        
        while(k-- > 0) {
            stack.pop();
        }
        
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        sb.reverse();
        
        while(sb.length() > 1 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }
        
        return sb.toString();
    }
}

Follow up