402. Remove K Digits

https://leetcode.com/problems/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) {
	Stack<Character> stack = new Stack<Character>();
	int i = 0;
	while (i < num.length()) {
	// evict bigger digits in the beginning
	while (k > 0 && !stack.isEmpty() && stack.peek() > num.charAt(i)) {
	stack.pop();
	k--;
	}
	stack.push(num.charAt(i++));
	}
	// corner cases like 1234 or 1111
	while (k > 0) {
	stack.pop();
	k--;
	}
	StringBuilder sb = new StringBuilder();
	while (!stack.isEmpty()) {
	sb.append(stack.pop());
	}
	//reverse stack order
	sb.reverse();
	StringBuilder ans = new StringBuilder();
	i = 0;
	// evict leading 0's
	while (i < sb.length() && sb.charAt(i) == '0') {
	i++;
	}
	while (i < sb.length()) {
	ans.append(sb.charAt(i++));
	}
	// return 0 for empty string
	return ans.length() > 0 ? ans.toString() : "0";
	}
	}

view raw 402.RemoveKDigits.java hosted with ❤ by GitHub