weeklychallenge | coding | python | perl | go

Return to Sender (Rejecting Repeated Letters Three Different Ways)

Yitzchak Scott-Thoennes

Yitzchak Scott-Thoennes

— 2 min read

Task 2: String Reduction:

You are given a word containing only alphabets,

 
Write a function that repeatedly removes adjacent duplicate characters from a string until no adjacent duplicates remain and return the final word.

Easy enough with a simple regex substitution using a backreference.

In Perl:

sub string_reduction($word) {
    1 while $word =~ s/(.)\1//g;
    return $word;
}

While the /g global flag does let it remove multiple duplicates in each pass, it still has to make multiple passes over the string until no more substitutions occur. Perl's substitution operator returns the number of substitutions made — for this purpose, more convenient than Python's re.sub, which returns the result of the substitutions rather than mutating the original string. (Perl does allow the modified string to be returned, rather than mutating the original, when given the /r flag.)

But with a simple recursive regex, you can achieve the final result with a single substitution.

In Python:

def string_reduction(word: str) -> str:
    return regex.sub(r'(.)(?R)*?\1', '', word)

(Recursive regexes are supported in regex, but not re.)

This, at first glance, may seem more efficient, but essentially has to scan to the end of the string for each character before knowing it shouldn't be removed, recursing for each step along the way. This is only a problem because, on failing to match, it starts afresh at the next character of the string; any determinations about what can be removed made in those recursions are lost.

Instead, we can make a single pass through the string, keeping a LIFO stack of not yet matched characters and matching and removing them when the latest of them is found (when all intervening parts of the string also qualify to be removed). Once at the end of the string, what remains in that stack is in fact the characters of the string to be returned.

In Go:

func StringReduction(word string) string {
    characters := []rune(word)
    num_characters := len(characters)
    num_kept := 0
    i := 0
    for i < num_characters {
        if i + 1 < num_characters && characters[i] == characters[i+1] {
            i += 2
        } else if num_kept > 0 && characters[i] == characters[num_kept-1] {
            i++
            num_kept--
        } else {
            characters[num_kept] = characters[i]
            num_kept++
            i++
        }
    }

    return string(characters[0:num_kept])
}

(Here we use the common Go pattern of applying a filter by assigning the kept values into the front of the input rather than going to the extra work of allocating/resizing a separate slice.)

Any of the three approaches can be used in any of the languages (e.g., using pcre2 in go for recursion), but I've tried to fit them to a language that illustrates them well.

full script, Python
full script, Go
full script, Perl

Comments greatly appreciated. See you next time.





Read more