https://zhengxucoding.wordpress.com/2015/04/19/minimum-number-formed-by-deleting-k-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.
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.
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.
http://massivealgorithms.blogspot.com/2015/06/lintcode-delete-digits-neverlandly.html
Read full article from 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.
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.
However, there are cases where we can not just select the minimum digit. For example, N = 32514, K = 2. We need to keep 3 digits. The most-left digit can not be 1 because we do no have enough digit to keep.
So our finding is that each time, we select a minimum digit such that there still have enough digits to keep. In the example where N = 32514 and K = 2, we need to keep 3 digits. First, we find the minimum of [3, 2, 5] because we need to have at least 2 digits on the right. It is 2. Then, we will find the minimum of [5, 1] because we need to find after the digit 2 and stop at 1 to keep 1 digit. After selecting 1 to keep, finally there is one selection, i.e., 4, to decide. Thus the minimum number can be obtained is 214.
public static String find(String input, int numDigitsToDelete){ if (numDigitsToDelete == 0){ return input; } else if (numDigitsToDelete >= input.length()){ return ""; } int numDigitLeft = input.length() - numDigitsToDelete; char[] result = new char[numDigitLeft]; int start = 0; int end = 0; for (int i = numDigitLeft; i >= 1; i--){ end = input.length() - i; int minIndex = getMinIndex(input, start, end); //update the digit to keep result[numDigitLeft - i] = input.charAt(minIndex); //update start for next windows start = minIndex + 1; } return String.valueOf(result);}private static int getMinIndex(String input, int start, int end){ char min = input.charAt(start); int minIndex = start; for (int i = start + 1; i <= end; i++){ //make sure compute the first (most left) if (input.charAt(i) < min){ min = input.charAt(i); minIndex = i; } } return minIndex;}7: public String generateLowestNumber(String S, int K) {
8: if (S == null || K > S.length()) {
9: return "";
10: }
11: // removing K digits is the same as keeping N - K digits
12: int add = S.length() - K; // the number of characters to add.
13: char[] lowest = new char[add];
14: // convert the input into an array of digits
15: int[] digits = new int[S.length()];
16: for (int i = 0; i < digits.length; i++) {
17: digits[i] = S.charAt(i) - '0';
18: }
19: int index = 0;
20: int[] closest = new int[S.length()];
21: closest[digits.length - 1] = -1;
22: for (int i = digits.length - 2; i >= 0; i--) {
23: int j = i + 1;
24: while (j != -1 && digits[i] <= digits[j]) {
25: j = closest[j];
26: }
27: closest[i] = j;
28: }
29: for (int i = 0; i < add; i++) {
30: int j = index;
31: while (j != -1 && j <= (digits.length - (add - i))) {
32: lowest[i] = (char) (digits[j] + (int) '0');
33: index = j;
34: j = closest[j];
35: }
36: index++;
37: }
38: return String.valueOf(lowest);
39: }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.
public static String getLeastNumberDeletingDigits_1(String number, int k) {
String leastNumber = number;
while(k > 0 && leastNumber.length() > 0) {
int firstDecreasingDigit = getFirstDecreasing(leastNumber);
if(firstDecreasingDigit >= 0) {
leastNumber = removeDigit(leastNumber, firstDecreasingDigit);
}
else {
leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);
}
--k;
}
return leastNumber;
}
private static int getFirstDecreasing(String number) {
for(int i = 0; i < number.length() - 1; ++i) {
int curDigit = number.charAt(i) - '0';
int nextDigit = number.charAt(i + 1) - '0';
if(curDigit > nextDigit) {
return i;
}
}
return -1;
}
private static String removeDigit(String number, int digitIndex) {
String result = "";
if(digitIndex > 0) {
result = number.substring(0, digitIndex);
}
if(digitIndex < number.length() - 1) {
result += number.substring(digitIndex + 1);
}
return result;
}
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 { // the value of
nextStart = number.length();
}
DecreasingResult result = new DecreasingResult();
result.firstDecreasing = firstDecreasing;
result.nextStart = nextStart;
return result;
}
http://www.geeksforgeeks.org/build-lowest-number-by-removing-n-digits-from-a-given-number/
since we can at most delete n characters, thus for any of (n+1) characters, there must be at least 1 character not being deleted.
And we process from left because of most significant bit is in left.
The idea is based on the fact that a character among first (n+1) characters must be there in resultant number. So we pick the smallest of first (n+1) digits and put it in result, and recur for remaining characters. Below is complete algorithm.
Initialize result as empty string
res = ""
buildLowestNumber(str, n, res)
1) If n == 0, then there is nothing to remove.
Append the whole 'str' to 'res' and return
2) Let 'len' be length of 'str'. If 'len' is smaller or equal
to n, then everything can be removed
Append nothing to 'res' and return
3) Find the smallest character among first (n+1) characters
of 'str'. Let the index of smallest character be minIndex.
Append 'str[minIndex]' to 'res' and recur for substring after
minIndex and for n = n-minIndex
buildLowestNumber(str[minIndex+1..len-1], n-minIndex).
void buildLowestNumberRec(string str, int n, string &res){ // If there are 0 characters to remove from str, // append everything to result if (n == 0) { res.append(str); return; } int len = str.length(); // If there are more characters to remove than string // length, then append nothing to result if (len <= n) return; // Find the smallest character among first (n+1) characters // of str. int minIndex = 0; for (int i = 1; i<=n ; i++) if (str[i] < str[minIndex]) minIndex = i; // Append the smallest character to result res.push_back(str[minIndex]); // substring starting from minIndex+1 to str.length() - 1. string new_str = str.substr(minIndex+1, len-minIndex); // Recur for the above substring and n equals to n-minIndex buildLowestNumberRec(new_str, n-minIndex, res);}// A wrapper over buildLowestNumberRec()string buildLowestNumber(string str, int n){ string res = ""; // Note that result is passed by reference buildLowestNumberRec(str, n, res); return res;}http://massivealgorithms.blogspot.com/2015/06/lintcode-delete-digits-neverlandly.html
Read full article from Coding Interview Questions: No. 48 - Least Number after Deleting Digits
