Chainlink CODE100 challlenge

Star challenge.md

Chainlink challenge

Given a string s, where * represents a star…

Remove the star along with its closest non-star character to its left in a single operation.

The task is to perform this operation until all stars have been removed and to return the string that remains.

Assumptions

• Input s is always a string and the characters are lowercase only
• There will be no consecutive stars (eg “ab***f”) - every star will be followed by a character or be the end of the string.
• Assume s has a length larger than 0 and smaller than 1000

Examples (test cases!)

chainlink → chainlink
chaa*inlinn*k → chainlink
abc*de*f  → abdf
a*b*c*d →  d
abcd → abcd
abc*de*  → abd

You can use this JSON object to test your function.

Submit your solutions at this gist - we'll pick the one we like the best and get you something nice.

This can be easily solved with stacks while parsing only once the given string.
If the current character is a star we can pop the head of the stack (aka the closest left hand side non-star character) and move on to the next one, otherwise just keep stacking the valid characters.

Here's an example of the implementation, in Java:

public String solve(final String s) {
    var stack = new Stack<Character>();
    for (var character : s.toCharArray()) {
        if (character == '*') {
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else {
            stack.push(character);
        }
    }
    var result = new StringBuilder();
    while (!stack.isEmpty()) {
        result.append(stack.pop());
    }
    return result.reverse().toString();
}

I've got 2 answers, one with regex, the other one without. You can choose the one you prefer!

private static String cleanStringRegex(String input) {
        return input.replaceAll(".\\*", "").replace("*", "");
    }

private static String cleanString(String input) {
        if (!input.contains("*")) {
            return input;
        }

        int index = input.indexOf("*");
        int pos = 0;

        StringBuilder result = new StringBuilder();

        //We don't want to change the input
        String tmpInput = input;

        //Clean up the * at the beginning of the string
        while (index == 0) {
            tmpInput = tmpInput.substring(1);
            index = tmpInput.indexOf("*");
        }

        while (index > 0) {
            result.append(tmpInput, pos, index-1);
            pos = index + 1;
            index = tmpInput.indexOf("*", pos);
        }
        //Don't forget the last part!
        result.append(tmpInput.substring(pos));

        return result.toString();

    }