Remove K Digits

LeetCode Q 402 - 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.

Solution

Solution 1 :

Delete one peak number at one time, and do k times.

Time Complexity: O(kn)

Code:

public String removeKdigits(String num, int k) {
	
	if (nums.length() <= k) return "0";

	while (k > 0) {
		
		int n = num.length();
		int i = 0;
		
		while (i < n - 1 && num.charAt(i) <= num.charAt(i + 1))
			i++;
		
		num = num.substring(0, i) + num.substring(i + 1, n);
		
		k--;
	}

	// trim leading zeros
	int index = 0;
	while (index < num.length() && num.charAt(index) == '0')
		index++;

	return index == num.length() ? "0" : num.substring(index, num.length());
}

Solution 2 : A more efficient solution

Use a stack to store the previous digits and check if previous one is larger than the current digit.

Time Complexity: O(n)

Code:

public String removeKdigits(String num, int k) {
	
	if (nums.length() <= k) return "0";

	int[] stk = new int[num.length()];
	int top = 0;

	for (int i = 0; i < num.length(); i++) {
		char ch = num.charAt(i);

		while (top > 0 && stk[top - 1] > ch && k > 0) {
			top--; k--;
		}

		stk[top++] = ch;
	}

	int index = 0;
	while (index < digits && stk[index] == '0')
		index++;

	return index == digits ? "0" : new String(stk, index, digits - index);
	//String​(char[] value, int offset, int count)
}