Task Requirements

A number between 0 and 1,000,000 and k that is smaller than the first number is given. When k amount of digit is removed, return the highest possible number.

My Attemps for Solution

No.1) Using Combination

On first thought, I wasn’t aware of how big the number could be, and came up with the idea to find all possiblities and to compare these to find the maximum value.

function solution(number, k) {
    let numbers = number.split('');
    let n = numbers.length;
    let indexArray = []]
    for(let i = 0; i < n; i++) {
        indexArray.push(i)
    };

    let max = 0;
    
    const combination = (array, target, n, r, count) => {
        if(r == 0) {
            let temp = numbers.slice();
            for(let i = 0, m = k; i < k; i++){
                temp.splice(target[i] - i, 1)
            }
            let current = temp.join('');
            max = (current > max) ? current : max
        } else if(n == 0 || n < r) return;
        else {
            combination(array, Object.assign([], target), n - 1, r, count + 1);
            target.push(array[count]);
            combination(array, Object.assign([], target), n - 1, r - 1, count + 1);
        }
    }
    
    combination(indexArray, [], n, k, 0)
    
    return max;
}

It worked well with the test cases, the longest of which was only 10 digits long. When submitted, it only worked with a few cases, and the rest was either timed out or returned Runtime Error. Through this experience, I learned that if recursion happens to many times, it causes runtime error.

No.2) Slicing the Number String

While struggling I came across a few discoveries, one of which was that the numbers that needs to be removed are those that are smaller than the follwing number. Using Loop, whenever the above case was encountered, the loop breaks, while creating a new number using slice to slice all the numbers before and after the removed number. However, this code still wasn’t efficient enough for certain cases.

No.3) Using Index and String Concatenation

With the help of the Q&A section, I came across a totally different approach, which is getting the largest value digit by digit. This is put in another word, a totally reversed approach.

The Logic

When selecting the largest number for each digit, what matters the most is leaving the minimum amount of numbers as it is, and selecting the largest from the rest of the numbers. Starting from the very beginning of the number we want to create, we select the largest number from the number set to take the place. However, this value cannot be in the index, where when this is selected, the numbers behind it does not suffice to fill the neccessary digits. Therefore, when one tries to create a 6 digit number from a originally 10 digit number, the first digit needs to be selected from the first five numbers. This is than done the same for all the digits.

Code

function solution(number, k) {
    let answer = '';
    let digits = number.length - k;
    let target = 0;

    let src_start = 0;
    let src_end =  number.length - digits + 1;

    while(answer.length != digits) {
        target = 0;

        for (let i = src_start; i < src_end; i++) {
            if (number[i] == 9) {
                target = 9;
                src_start = i + 1
                break;
            }
            if(number[i] > target){
                target = number[i];
                src_start = i + 1;
            }
        }

        answer += target;
        src_end++;
    }

Explanation

In order to restrict the source of numbers, from which to select from, I used the start and end variables. Until the answer string is long as the desired digits, the loop is repeated. In this loop, from the restricted pool, an maximum number is selected. If the indicator encounters 9, which is the largest number possible, the loop stops (Optimization). When the largest number is selected, the starting index for the source pool is assigned as index of the number plus one. The end index is pushed one, since a digit is selected, and therefore one less digit is needed.