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.

How to submit ? Put it here in the comment ?

Yes that is the easiest.

…

On Fri, 24 May 2024, 16:00 Agung Sidharta So, ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ How to submit ? Put it here in the comment ? — Reply to this email directly, view it on GitHub <https://gist.github.com/codepo8/cdc70adf1740540d07ff9b24783ae1dd#gistcomment-5067714> or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAADJRBPTQ5WXFQPCTZUNG3ZD5BWDBFKMF2HI4TJMJ2XIZLTSKBKK5TBNR2WLJDUOJ2WLJDOMFWWLO3UNBZGKYLEL5YGC4TUNFRWS4DBNZ2F6YLDORUXM2LUPGBKK5TBNR2WLJDHNFZXJJDOMFWWLK3UNBZGKYLEL52HS4DFVRZXKYTKMVRXIX3UPFYGLK2HNFZXIQ3PNVWWK3TUUZ2G64DJMNZZDAVEOR4XAZNEM5UXG5FFOZQWY5LFVEYTGMBUGIZDANJSU52HE2LHM5SXFJTDOJSWC5DF> . You are receiving this email because you authored the thread. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub> .

If you're shy about your code, you can also email it to me. On Fri, 24 May 2024, 16:38 Christian Heilmann, ***@***.***> wrote:

…

Yes that is the easiest. On Fri, 24 May 2024, 16:00 Agung Sidharta So, ***@***.***> wrote: > ***@***.**** commented on this gist. > ------------------------------ > > How to submit ? Put it here in the comment ? > > — > Reply to this email directly, view it on GitHub > <https://gist.github.com/codepo8/cdc70adf1740540d07ff9b24783ae1dd#gistcomment-5067714> > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AAADJRBPTQ5WXFQPCTZUNG3ZD5BWDBFKMF2HI4TJMJ2XIZLTSKBKK5TBNR2WLJDUOJ2WLJDOMFWWLO3UNBZGKYLEL5YGC4TUNFRWS4DBNZ2F6YLDORUXM2LUPGBKK5TBNR2WLJDHNFZXJJDOMFWWLK3UNBZGKYLEL52HS4DFVRZXKYTKMVRXIX3UPFYGLK2HNFZXIQ3PNVWWK3TUUZ2G64DJMNZZDAVEOR4XAZNEM5UXG5FFOZQWY5LFVEYTGMBUGIZDANJSU52HE2LHM5SXFJTDOJSWC5DF> > . > You are receiving this email because you authored the thread. > > Triage notifications on the go with GitHub Mobile for iOS > <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> > or Android > <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub> > . > >

Is python OK ? I believe the result of test case abc*d should be "d" (without space).

import re
def star_removal(s):
    return re.sub('[a-z]\*', '', s)
    
test = [
    {"input":"chainlink","result":"chainlink"},
    {"input":"chaa*inlinn*k","result":"chainlink"},
    {"input":"abc*de*f ","result":"abdf"},
    {"input":"a*b*c*d","result":" d"},
    {"input":"abcd","result":"abcd"},
    {"input":"abc*de*","result":"abd"}
]

for t in test:
    print(star_removal(t["input"]) + " -> " + t["result"])

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();

    }