Lintcode: Delete Digits

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

N <= 240 and k <= N,

Have you met this question in a real interview?

Yes

Example

Given an integer A = "178542", k = 4

return a string "12"

Tags Expand 

Greedy LintCode Copyright

Related Problems Expand 

MediumLargest Number17 %

Initial thoughts(wrong):

Compare the effects of each digit in A. So we need to sort the digits. The effect can be measured the number after removing the corresponding digit from A.
However, this solution is wrong. Because each time we delete one digit, the effect of each digit removal has already changed. If we update the effect array each time we delete one digit, Time complexity will become O(knlogn).
Terrible solution...
Below is the wrong solution and wrong test result:

class Solution {
public:
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
    */
    static bool comp(pair<int, string> p1, pair<int, string> p2){
        return p1.second < p2.second;
    }
     
    string DeleteDigits(string A, int k) {
        // wirte your code here
        vector< pair<int, string> > digVal;
        for(int i = 0; i < A.size(); i++){
            string str = A;
            str.erase(i, 1);
            pair<int, string> p = make_pair(i, str);
            digVal.push_back(p);
        }
        sort(digVal.begin(), digVal.end(), comp);
        for(int i = 0; i < k; i++){
            A.replace(digVal[i].first, 1, "t");
        }
        for(int i = 0; i < A.size(); i++){
            if(A[i] == 't') A.erase(i--, 1);
        }
        return A;
    }
};

Input

178542, 4

Output

17

Expected

12

Second try: Greedy
Now we know each time we delete one digit, we have to research the next element we should delete.
To make the result as small as possible, the deletion has to start from the left side.
When we delete one digit, it will be replaced by the digit behind it. So if we want the number to be smaller, we need delete the first digit that is larger than the digit behind itself. If we cannot find one, just delete the last digit.
Time: O(kn)
space: O(1)
e.g.  178542      delete 8 ==>  17542  delete 7  ==> 1542 delete 5 ==> 142 delete 4 ==> 12

class Solution {
public:
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    string DeleteDigits(string A, int k) {
        // wirte your code here
        for(int i = 0; i < k; i++){
            for(int j = 0; j < A.size(); j++){
                if(j == A.size() -1 || A[j] > A[j + 1]){
                A.erase(j, 1);
                break;
                }
            }
        }
        while(A.front() == '0'){
            A.erase(0,1);
        }
        return A;
    }
};

Optimized Greedy -- two pointers:
In the above codes, each loop starts comparison from 0. Actually it's not necessary. Numbers already compared don't need to be compared again. We can use j to record it.
Worst time: O(2n) ----e.g. input (123451, 6)
Space: O(1)

class Solution {
public:
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    string DeleteDigits(string A, int k) {
        // wirte your code here
        int j = 0;
        for(int i = 0; i < k; i++){
            for(; j < A.size(); j++){
                if(j == A.size() -1 || A[j] > A[j + 1]){
                    A.erase(j,1);
                    j--;
                    if(j == -1) j = 0; //in case j= 0, then j-- be -1
                    break;
                }
            }
        }
        while(A.front() == '0'){
            A.erase(0,1);
        }
        return A;
    }
};

Optimized Greedy -- stack:
Use a stack to remember those numbers which have been compared.
Worst time: O(2n) -- e.g. input (123451, 6)
Space: O(n)
http://www.cnblogs.com/easonliu/p/4507657.html
STL--string.substr()
STL--string.erase()

The thoughts are a little different;
Before storing each digit from left to right, it will check whether the top element in stack is larger than current digit:
 if larger, keep poping until there is one element in the stack is small or equal to the current digit or the stack is empty, then push current digit,
 if not, just push current element.
The method above makes sure all elements stored in stack are sorted from small to large, by poping all large elements before pushing new element.
However, this method means we only do element removal when new element is small than top element in stack. Which means the removal times may be smaller than k.
For sorted digits from small to big,  we just need to delete the last element to get the smallest number.

Deal with exceptions: How to push 0:
Two cases:
when the new coming element is 0, then all elements in stack will be cleared except count == k
If 0 is the first element in stack, we don't need this 0
If count already equals to k and stack is not empty, we need this 0
So we need 0 when stack is not empty, don't need 0 when stack is empty.
Logical relationship above is (A[i] != '0' || !str.empty()) in Line 17

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: /** *@param A: A positive integer which has N digits, A is a string. *@param k: Remove k digits. *@return: A string */ string DeleteDigits(string A, int k) { string str; int count = 0; for(int i = 0; i < A.size(); i++){ while(!str.empty() && str.back() > A[i] && count < k){ str.pop_back(); count++; } //if 0 appear, all elements in stack will be cleared except c=k if(A[i] != '0' || !str.empty()) str.push_back(A[i]); } //in case, when all numbers in stack are already from low to high //just delete from the end if(count < k) str.erase(str.end() - (k - count), str.end()); return str; } };

Try DP and DFS solution: even though they are not good one

http://blog.csdn.net/wankunde/article/details/43792369