The Weekly Challenge 346

The Strategy: Use a stack of indices, seeded with -1 as a sentinel. Push indices of opening parentheses. For each closing parenthesis, pop from the stack and compute the distance from the current index to the new stack top. When the stack empties after a pop, push the current index to mark the boundary of the next candidate. This is a classic O(n) linear scan.

sub longest_parenthesis ($str_input) {
    state $check = compile( StrMatch [qr/\A[()]*\z/] );
    my ($str) = $check->($str_input);

    my $length = length $str;
    return 0 if $length == 0;

    my @stack   = (-1);
    my $longest = 0;

    for my $idx ( 0 .. $length - 1 ) {
        my $char = substr $str, $idx, 1;

        if ( $char eq '(' ) {
            push @stack, $idx;
            next;
        }

        pop @stack;
        if (@stack) {
            my $candidate = $idx - $stack[-1];
            $longest = $candidate if $candidate > $longest;
        }
        else {
            push @stack, $idx;
        }
    }

    return $longest;
}

def longest_parenthesis(text: str) -> int:
    """Return the length of the longest valid parenthesis substring."""
    stack = [-1]
    longest = 0

    for i, ch in enumerate(text):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if stack:
                longest = max(longest, i - stack[-1])
            else:
                stack.append(i)
    return longest

The Strategy: Depth-first backtracking over all possible digit partitions. For each partition, try all three operators. To handle multiplication precedence correctly without a full parser, track both the running total and the last operand. When inserting multiplication, rewind the previous operand from the total and replace it with the product. Skip numbers with leading zeros (except single digit 0).

sub magic_expression ( $digits_input, $target_input ) {
    state $check = compile( StrMatch [qr/\A\d+\z/], Int );
    my ( $digits, $target ) = $check->( $digits_input, $target_input );

    my $length = length $digits;
    my @results;

    my $search;
    $search = sub ( $pos, $expression, $value, $last_operand ) {
        if ( $pos == $length ) {
            push @results, $expression if $value == $target;
            return;
        }

        for my $end ( $pos + 1 .. $length ) {
            my $chunk = substr $digits, $pos, $end - $pos;
            next if length($chunk) > 1 && substr( $chunk, 0, 1 ) eq '0';
            my $number = 0 + $chunk;

            if ( $pos == 0 ) {
                $search->( $end, $chunk, $number, $number );
                next;
            }

            $search->( $end, "$expression+$chunk", $value + $number, $number );
            $search->( $end, "$expression-$chunk", $value - $number, -$number );

            my $product = $last_operand * $number;
            $search->( $end, "$expression*$chunk", $value - $last_operand + $product, $product );
        }
    };

    $search->( 0, q{}, 0, 0 );
    @results = sort @results;

    return \@results;
}

def magic_expression(digits: str, target: int) -> list[str]:
    """Find all expressions inserting +, -, * that equal target."""
    results: list[str] = []

    def search(pos: int, expr: str, value: int, last: int) -> None:
        if pos == len(digits):
            if value == target:
                results.append(expr)
            return

        for end in range(pos + 1, len(digits) + 1):
            chunk = digits[pos:end]
            if len(chunk) > 1 and chunk[0] == "0":
                continue
            number = int(chunk)

            if pos == 0:
                search(end, chunk, number, number)
                continue

            search(end, f"{expr}+{chunk}", value + number, number)
            search(end, f"{expr}-{chunk}", value - number, -number)
            product = last * number
            search(end, f"{expr}*{chunk}", value - last + product, product)

    search(0, "", 0, 0)
    return sorted(results)