## Saturday, October 8, 2016

### LeetCode OJ - Remove K Digits

Problem:

Analysis:

The key is to minimize the significant digits. If the first digits are 12, there is no reason to eliminate 1 because 1xx is always better than 2xx.

On the other hand, if the sequence is 123214, there is no reason not to eliminate the 3 either, since 122xx is always better than 123xx, and there is no way to obtain 12xxx < 123xx without eliminating the 3.

Solution:

The analysis above indicate we are unwilling to eliminate the first digits of an increasing sequence but wanted to eliminate the digit that start a decreasing sequence.

Therefore the algorithm maintains a stack of increasing indices. Whenever we hit the top of the stack (i.e. there is no way I can add more digits without going down (or ends the array)), we remove it.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/remove-k-digits/

#include "LEET_REMOVE_K_DIGITS.h"
#include <stack>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_REMOVE_K_DIGITS
{
class Solution
{
public:
string removeKdigits(string num, int k)
{
if (k >= num.size())
{
return "0";
}
stack<int> increasing_indice;
int i = 0;
while (k > 0)
{
while (true)
{
if (increasing_indice.size() == 0)
{
increasing_indice.push(i++);
}
else if (num[i] >= num[increasing_indice.top()])
{
increasing_indice.push(i++);
}
else
{
break;
}
}
int index_to_remove = increasing_indice.top();
num[index_to_remove] = ' ';
increasing_indice.pop();
k--;
}

char* resultBuffer = new char[num.size() - k + 1];
size_t j = 0;
for (size_t i = 0; i < num.size(); i++)
{
if (num[i] != ' ')
{
if (!leading || num[i] != '0')
{
resultBuffer[j++] = num[i];
}
}
}

{
resultBuffer[j++] = '0';
}

resultBuffer[j++] = '\0';
string resultString(resultBuffer);
delete[] resultBuffer;
return resultString;
}
};
};

using namespace _LEET_REMOVE_K_DIGITS;

int LEET_REMOVE_K_DIGITS()
{
Solution solution;
cout << solution.removeKdigits("1432219", 3) << endl;
cout << solution.removeKdigits("10200", 1) << endl;
cout << solution.removeKdigits("10", 2) << endl;
return 0;
}