Remove K Digits

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.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

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:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output 
must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing 
which is 0.

 class Solution {
    public String removeKdigits(String num, int k) {
        for (int i = 1; i <= k; i++)
            num = toRemoveOneDigit(num);
        return num;
    }

    private String toRemoveOneDigit(String num) {
        int length = num.length();
        int index = length - 1;
        for (int i = 0; i < index; i++) {
            if (num.charAt(i) > num.charAt(i + 1)) {
                index = i;
                break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            char digit = num.charAt(i);
            if (sb.length() == 0 && digit == '0' || i == index)
                continue;
            sb.append(digit);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

Try it on Leetcode

Here, we are going to check till K position. Within these position, we can find the smallest possible number.

1) While iterating from 1 to K in a given string, for each iteration we are going to remove one digit from a string.

2) In removeOneDigit(), iterate the passed string.

 a) In given string if digit at i is greater than i+1, then store than i positon.

 b) Now the second for loop [mainly to remove particular digit in the string] [we can also do this operation with substring concept, but if there is any leading zeroes also we need to remove, so in this case for-loop provides easy way to finish it] in the method, will update the string by removing that particular digit at i position.

3) Repeat steps 1, 2 till K in a given string.

4) Finally return the updated string.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation


Please let us know your views in comment section

Subscribe us to receive updates instantly..

Happy Coding..!!