Coding Interview Questions: No. 48 - Least Number after Deleting Digits
Problem: Please get the least number after deleting k digits from the input number. For example, if the input number is 24635, the least number is 23 after deleting 3 digits.
Now we get the rules to delete digits to get the least remaining number: If there are digits who are greater than the next one, delete the first digit. If all digits in the number are increasingly sorted, delete the last digit gets deleted. The process repeats until the required k digits are deleted.
Problem: Please get the least number after deleting k digits from the input number. For example, if the input number is 24635, the least number is 23 after deleting 3 digits.
Now we get the rules to delete digits to get the least remaining number: If there are digits who are greater than the next one, delete the first digit. If all digits in the number are increasingly sorted, delete the last digit gets deleted. The process repeats until the required k digits are deleted.
Optimization: Save the start index for the next round of search for the first decreasing digit
In the method getFirstDecreasing above to get the first digit which is greater than the next one, we always start from the first digit. Is it necessary to start over in every round of search?
The answer is no. If the ith digit is the first digit which is greater than the next one, all digits before the ith digit are increasingly sorted. The (i-1)th digit might be less than the (i+1)th digit, the next digit of the (i-1)th digit after the ith digit is deleted. Therefore, it is safe to start from the (i-1)th digit in the next round of search.
With this optimization strategy, the efficiency gets improved from O(n*k) to O(n), if the length of the input number has n digits and k digits are deleted.
class DecreasingResult {
public int firstDecreasing;
public int nextStart;
}
public static String getLeastNumberDeletingDigits_2(String number, int k) {
String leastNumber = number;
int start = 0;
while(k > 0 && leastNumber.length() > 0) {
DecreasingResult result = getNextDecreasing(leastNumber, start);
if(result.firstDecreasing >= 0) {
leastNumber = removeDigit(leastNumber, result.firstDecreasing);
}
else {
leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);
}
start = result.nextStart;
--k;
}
return leastNumber;
}
private static DecreasingResult getNextDecreasing(String number, int start) {
int firstDecreasing = -1;
int nextStart;
for(int i = start; i < number.length() - 1; ++i) {
int curDigit = number.charAt(i) - '0';
int nextDigit = number.charAt(i + 1) - '0';
if(curDigit > nextDigit) {
firstDecreasing = i;
break;
}
}
if(firstDecreasing == 0) {
nextStart = 0;
}
else if (firstDecreasing > 0) {
nextStart = firstDecreasing - 1;
}
else {
nextStart = number.length();
}
DecreasingResult result = new DecreasingResult();
result.firstDecreasing = firstDecreasing;
result.nextStart = nextStart;
return result;
}
Read full article from Coding Interview Questions: No. 48 - Least Number after Deleting Digits