0212EasyStringStack

Settle the Loom Tape

Tracked in this browser only

Trains the technique from

LeetCode 1047Remove All Adjacent Duplicates In String

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 jacquard loom runs off a punched tape. Every hole in the tape carries one shed code, written as a single lowercase letter, and the loom reads the codes in order starting from the head of the tape.

The loom has a quirk. Whenever two holes sitting side by side carry the same code, the second one undoes the first, so the loom throws that pair away. The tape then closes up around the gap, which can bring two codes that were held apart into contact, and those two may cancel in their turn. The loom goes on discarding pairs for as long as it can find one.

Given the tape as the string tape, return the codes still punched on it once no two neighbouring holes carry the same code. The settled tape can come back empty. Whichever pair the loom happens to discard first, the codes it finishes with are the same, so there is a single answer to report.

Examples

Example 1

Input: tape = "mnnmpq"
Output: "pq"

The pair of n codes goes first, which leaves the two m codes touching, and they go next. What is left is p followed by q, and those two differ.

Example 2

Input: tape = "rrsttsu"
Output: "u"

The r pair goes, then the t pair, which brings the two s codes together and they go as well, leaving u on its own.

Example 3

Input: tape = "kdvvdk"
Output: ""

The v pair goes, then the d pair, then the k pair, so the loom is left with a bare tape.

Constraints

1 <= tape.length <= 10^5
tape consists of lowercase English letters.

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 settle_the_loom_tape(tape: str) -> str:

Java

public String settleTheLoomTape(String tape)

The intended approach

Time O(n)Space O(n)

Read the codes once, keeping a pile of the codes that have survived so far. A code whose match is already on top of the pile cancels it, so pop instead of pushing; otherwise the code goes on the pile. Because the pile always ends with the code a new one would touch after every earlier cancellation, the cascade is handled as it happens rather than by rescanning, and the pile read bottom to top is the settled tape.

Pythonentry point: settle_the_loom_tape

def settle_the_loom_tape(tape):
    # Time: O(n) -- every code is pushed at most once and popped at most once.
    # Space: O(n) -- the pile of surviving codes, which is also the answer.
    kept = []
    for code in tape:
        if kept and kept[-1] == code:
            kept.pop()
        else:
            kept.append(code)
    return "".join(kept)

The obvious version

Scan for the leftmost neighbouring pair carrying the same code, splice it out, and start scanning again from the head, repeating until a full scan finds nothing. O(n^2).

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_settle_the_loom_tape(tape):
    codes = list(tape)
    while True:
        hit = -1
        for i in range(len(codes) - 1):
            if codes[i] == codes[i + 1]:
                hit = i
                break
        if hit < 0:
            return "".join(codes)
        codes = codes[:hit] + codes[hit + 2:]

How this problem was checked

Reference solution executed against 15 test cases — 15 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