Remove K Digits to build lowest number from a given number

Problem: Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Example:

Input: num = "12145", k = 1
Output: "1145"
Explanation: Removing 2 to form the new number 1145 which is the smallest.

Approach: Let's understand the approach using examples:

Say num = "1234" and k = 1

You can see in the above example that removing 4 will solve the problem that is removing 4 will form the lowest number "123". 

Another example: num = "1324" and k = 1

Removing 3 will from the lowest number. 

If you see there is a pattern, if all the digits are in increasing order, we remove the last digit. If not, we just to see where the increasing order is being broken and we just remove the greater digit of two, that is if num[i] > num[i+1], Remove num[i].

We can do the same step k times to achieve the result or we can use extra storage like stack or deque to reduce the run time.

That's all!

Implementation in C#:

        public static string RemoveKdigits(string num, int k)

        {

            if (num.Length <= k)

            {

                return "0";

            }

            // Using LinkedList as C# has no deque

            LinkedList<char> deque = new LinkedList<char>();

            deque.AddLast(num[0]);

            for (int i = 1; i < num.Length; ++i)

            {

                if (num[i] >= deque.Last())

                {

                    deque.AddLast(num[i]);

                }

                else

                {

                    while (k > 0 && deque.Count > 0 && num[i] < deque.Last())

                    {

                        --k;

                        deque.RemoveLast();

                    }

                    deque.AddLast(num[i]);

                }

            }

            while (k > 0 && deque.Count > 0)

            {

                --k;

                deque.RemoveLast();

            }

            string result = string.Empty;

            bool isDigitAppeared = false;

            for (LinkedListNode<char> it = deque.First; it != null; it = it.Next)

            {

                if (it.Value == '0' && !isDigitAppeared)

                {

                    continue;

                }

                isDigitAppeared = true;

                result += it.Value;

            }

            return result.Length > 0 ? result  : "0";

        }

Complexity: O(n)