Algorithm

LintCode/Delete Digits

Problem Summary

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. k ≤ N ≤ 240.

Solution

Removing k digits is actually choosing N-k digits to form a new integer.

Apparently, we should make the top digit minimal.
For any i, 0 ≤ i < N-k, we greedily choose the smallest digit in current range.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    /*
     * @param A: A positive integer which has N digits, A is a string
     * @param l: Remove k digits
     * @return: A string
     */
    string DeleteDigits(string &A, int l) {
    	string res;
        int n = A.length();
        int st = 0;
        for (int i = 0; i < n-l; ++i)
        {
            int k = st, en = l+i;
            for (int j = st+1; j <= en; ++j)
                if (A[j]<A[k])
                    k = j;
            
            res += A[k];
            st = k+1;
        }
        while (res.length()>1 && res[0] == '0')
            res.erase(res.begin());
    	return res;
    }
};