If there are no zeros, you can use a greedy strategy: Go left to right and look at each digit one by one. You remove a digit if it is the last digit or if it is larger than the next digit. After removing a digit, you go back one step and look at the previous digit again. This is so that in a case like 22221 you will remove all of the 2's before removing the 1.

For example with 1432219:

• At (1)432219, you don't remove the 1.
• At 1(4)32219, you remove the 4 because it is larger than the next digit, 3.
• At (1)32219, you don't remove the 1.
• At 1(3)2219, you remove the 3.
• At (1)2219, you don't remove the 1.
• At 1(2)219, you don't remove the 2.
• At 12(2)19, you remove the 2 because it's larger than the next digit.
• At 1(2)19, you remove the 2 again.
• At (1)19, you don't remove.
• At 1(1)9, you don't remove.
• At 11(9), you remove the 9 because it's the last digit.

Etc., so for 1432219 and k=1,2,... you get 1432219, 132219, 12219, 1219, 119, 11, 1.

If there are zeros in the input, I'm not yet sure if this strategy works without modification or if there are some corner cases.

Edit: I think this strategy should work without changes even when the input contains zeros.

Simple greedy, find smallest number that can be first, then second, and so on. For this you can use segment tree to find min, or you can store each occurence of digits and erase them one by one.

see here: http://junhaolin.com/Leetcode_Remove_K_Digits.html

here is the simple implementation using stack. The algorithm is already explained in the above comments.

string removeKdigits(string s, int k) {
        stack<char> stk;
        int n = s.length();
        int i ,j;
        if( k == n )
        	return "0";
        string ans;
        stk.push( s[0] );
        for( i = 1 ; i < n && k > 0 ; i++ ){
            	if( stk.empty() || s[i] >= stk.top()  ){
        		bool f = true;
                if( s[i] == '0' && stk.empty() )
                    f = false;
                if( f )
                    stk.push( s[i] );
        	}
        	else{
        		while( k > 0 && !stk.empty() && s[i] < stk.top() ){
        			k--;
        			stk.pop();
        		}
        		bool f = true;
                if( s[i] == '0' && stk.empty() )
                    f = false;
                if( f )
                    stk.push( s[i] );
        	}
        }
        while( k > 0 ){
        	stk.pop();
        	k--;
        }
        while( !stk.empty() ){
        	ans += stk.top();
        	stk.pop();
        }
        reverse(ans.begin(),ans.end());
        if( ans.length() == 0 ){
        	while( i < n && s[i] == '0' )
        		i++;
        }
        while( i < n ){
        	ans += s[i];
        	i++;
        }
        return ans.length() ? ans : "0";
}