Remove All Adjacent Duplicates In String
Real-world version: Settle the Loom TapeThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def settle_the_loom_tape(tape: str) -> str:public String settleTheLoomTape(String tape)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's