0396EasyTwo PointersStringStackSimulation

Strike Marks On Two Tapes

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.

Two field radios each punch a row of characters onto its own paper tape. A lowercase letter is punched as itself. The character # is a strike mark, and it cancels the nearest letter to its left that no earlier strike mark has already cancelled. A strike mark with no letter left to cancel does nothing at all, and it is never an error.

The reading of a tape is the row of letters that survive, left to right, once every strike mark has been honoured.

Given tapes s and t, return true when the two tapes have the same reading and false otherwise.

Do it in O(1) extra space: work from the cursors you keep, without assembling either reading.

Examples

Example 1

Input: s = "gold#s", t = "gol#ls"
Output: true

Tape `s` loses its `d`, so it reads `gols`. Tape `t` loses its first `l`, then punches `l` and `s`, so it also reads `gols`.

Example 2

Input: s = "note#", t = "not#e"
Output: false

Tape `s` reads `not` and tape `t` reads `noe`, and those two readings differ.

Example 3

Input: s = "pq##", t = "r#w#"
Output: true

The two strike marks on `s` cancel `q` and then `p`, so `s` reads as nothing. Each strike mark on `t` cancels the letter before it, so `t` also reads as nothing.

Example 4

Input: s = "###hive", t = "hive"
Output: true

The three leading strike marks on `s` have no letters to their left, so they do nothing, and both tapes read `hive`.

Constraints

1 <= s.length, t.length <= 200
s and t contain only lowercase English letters and the character '#'.

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 backspace_compare(s: str, t: str) -> bool:

Java

public boolean backspaceCompare(String s, String t)

The intended approach

Time O(n + m) where n and m are the tape lengthsSpace O(1)

Read both tapes right to left, since a strike mark only ever affects letters already behind the cursor. On each tape, count strike marks as they appear and consume that many letters before exposing the next surviving one, using a loop so a run of strike marks swallows a run of letters. Compare the two exposed letters, and report failure if one tape exposes a letter while the other has run out.

Pythonentry point: backspace_compare

def backspace_compare(s, t):
    # Time O(len(s) + len(t)): each index of each tape is visited once.
    # Space O(1): only four integer cursors, no rebuilt tape.
    i = len(s) - 1
    j = len(t) - 1
    pending_s = 0
    pending_t = 0
    while i >= 0 or j >= 0:
        while i >= 0:
            if s[i] == '#':
                pending_s += 1
                i -= 1
            elif pending_s > 0:
                pending_s -= 1
                i -= 1
            else:
                break
        while j >= 0:
            if t[j] == '#':
                pending_t += 1
                j -= 1
            elif pending_t > 0:
                pending_t -= 1
                j -= 1
            else:
                break
        if i >= 0 and j >= 0:
            if s[i] != t[j]:
                return False
        elif i >= 0 or j >= 0:
            return False
        i -= 1
        j -= 1
    return True

The obvious version

Push letters onto a list while scanning each tape left to right and pop on a strike mark, then compare the two assembled readings.

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_backspace_compare(s, t):
    def decode(tape):
        out = []
        for ch in tape:
            if ch == '#':
                if out:
                    out.pop()
            else:
                out.append(ch)
        return out

    return decode(s) == decode(t)

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
4 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