0107MediumStringDynamic ProgrammingStackGreedyBracket Sequences

Salvage a Smudged Span Trace

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A packaging tool records a trace while it walks a project. It writes ( when it enters a span and ) when it leaves one, and a leaving mark always settles the span that was entered most recently and is still open. A trace is sound when every leaving mark settles some earlier entering mark and no span is left open once the trace runs out.

One run wrote to a failing disk, so a few bytes came back smudged. A smudged byte is recorded as *, and each one may have held an entering mark, a leaving mark, or no mark at all. Two smudged bytes need not be read the same way.

You are handed the recovered trace s. Return true when at least one reading of the smudged bytes leaves a sound trace, and false when no reading does.

Examples

Example 1

Input: s = "((**))"
Output: true

Read both smudged bytes as carrying no mark and the trace becomes two entering marks followed by two leaving marks, which is sound.

Example 2

Input: s = "*)(("
Output: false

The trace finishes with two entering marks and nothing after them, so two spans stay open no matter how the leading smudge is read.

Example 3

Input: s = "**"
Output: true

Reading both bytes as carrying no mark leaves an empty trace, which is sound; reading the first as entering and the second as leaving works too.

Constraints

1 <= s.length <= 100
Every character of `s` is `(`, `)` or `*`.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def trace_is_recoverable(s: str) -> bool:

Java

public boolean traceIsRecoverable(String s)

The intended approach

Time O(n)Space O(1)

Instead of tracking every reading, track the range of span counts that could still be open. An entering mark lifts both ends of the range, a leaving mark drops both, and a smudged byte widens the range by one in each direction. If the top of the range ever falls below zero, some leaving mark cannot be settled and no reading survives; the bottom is clamped at zero because readings that would go negative are simply discarded. The trace is recoverable exactly when zero is still reachable at the end.

Pythonentry point: trace_is_recoverable

def trace_is_recoverable(s):
    low = 0
    high = 0
    for mark in s:
        if mark == "(":
            low += 1
            high += 1
        elif mark == ")":
            low -= 1
            high -= 1
        else:
            low -= 1
            high += 1
        if high < 0:
            return False
        if low < 0:
            low = 0
    return low == 0

The obvious version

Carry the whole set of reachable open-span counts forward one byte at a time, branching a smudged byte into all three readings. Correct by construction and O(n^2) in the worst case since the set can hold up to n counts.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_trace_is_recoverable(s):
    open_counts = {0}
    for mark in s:
        nxt = set()
        for held in open_counts:
            if mark == "(":
                nxt.add(held + 1)
            elif mark == ")":
                if held > 0:
                    nxt.add(held - 1)
            else:
                nxt.add(held + 1)
                nxt.add(held)
                if held > 0:
                    nxt.add(held - 1)
        open_counts = nxt
        if not open_counts:
            return False
    return 0 in open_counts

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in