Perl Weekly Challenge 328 - Replace All ? and Good String

Task 1: Replace All ?

"The Character Puzzle: Filling in the Blanks!"

Replace every '?' character with a lowercase letter such that no two adjacent characters are the same.

The Strategy: Iterate through the string character by character. When a '?' is found, check the characters immediately before and after it (if they exist). Pick the first letter from 'a' to 'z' that doesn't match either neighbor and use it to replace the '?'. This greedy approach ensures the constraint is satisfied with minimal overhead.

Perl Implementation

sub replace_question_marks {
    my ($str) = @_;
    my @chars = split //, $str;
    my $len   = @chars;
    for my $i (0 .. $len - 1) {
        next unless $chars[$i] eq '?';
        my $prev = $i > 0        ? $chars[$i - 1] : '';
        my $next = $i < $len - 1 ? $chars[$i + 1] : '';
        for my $candidate ('a' .. 'z') {
            next if $candidate eq $prev;
            next if $candidate eq $next;
            $chars[$i] = $candidate;
            last;
        }
    }
    return join '', @chars;
}

Python Implementation

def replace_question_marks(text: str) -> str:
    chars = list(text)
    for i, ch in enumerate(chars):
        if ch != "?":
            continue
        prev_ch = chars[i - 1] if i > 0 else ""
        next_ch = chars[i + 1] if i < len(chars) - 1 else ""
        for cand in string.ascii_lowercase:
            if cand != prev_ch and cand != next_ch:
                chars[i] = cand
                break
    return "".join(chars)

Task 2: Good String

"Opposite Attraction: Cleaning Up Character Pairs!"

A string is "good" if it doesn't contain any adjacent pairs of the same letter in different cases (like 'aA' or 'Aa'). Remove these pairs until none remain.

The Strategy: A stack is perfect for this problem. We process each character of the string one by one. Before pushing a character onto the stack, we compare it with the character at the top of the stack. If they are the same letter (case-insensitive) but have different cases (not equal), they cancel each other out, and we pop the stack. Otherwise, we push the current character.

Perl Implementation

sub good_string {
    my ($s) = @_;
    my @stack;
    for my $ch (split //, $s) {
        if (@stack && lc($stack[-1]) eq lc($ch) && $stack[-1] ne $ch) {
            pop @stack;
        }
        else {
            push @stack, $ch;
        }
    }
    return join '', @stack;
}

Python Implementation

def good_string(text: str) -> str:
    stack: list[str] = []
    for ch in text:
        if stack and stack[-1].lower() == ch.lower() and stack[-1] != ch:
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)