0622EasyStringStackSimulation

Cancelling Paint Marks

Tracked in this browser only

Trains the technique from

LeetCode 2696Minimum String Length After Removing Substrings

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 calibration strip carries a row of paint marks, given as the uppercase string s.

Two marks that sit next to each other cancel when the left one is 'R' and the right one is 'B', or when the left one is 'G' and the right one is 'Y'. Order matters: "BR" and "YG" do not cancel.

You may repeatedly pick any cancelling pair, erase both of its marks, and let the two sides of the strip close up so that the marks that were on either side become neighbours. Return the smallest length the strip can be reduced to.

Examples

Example 1

Input: s = "RGYB"
Output: 0

Erasing the `"GY"` in the middle leaves `"RB"`, which cancels as well, so nothing is left.

Example 2

Input: s = "BRGY"
Output: 2

Erasing the `"GY"` leaves `"BR"`. Blue before red is not a cancelling pair, so two marks remain.

Example 3

Input: s = "KRBK"
Output: 2

The `"RB"` in the middle cancels and the two `'K'` marks close up next to each other. `'K'` is in no cancelling pair, so the strip stops at length 2.

Constraints

1 <= s.length <= 100
s consists only of uppercase 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 min_length(s: str) -> int:

Java

public int minLength(String s)

The intended approach

Time O(n) — one pass with a constant amount of work per mark.Space O(n) for the stack of surviving marks.

One sweep across the strip maintains a stack of the marks that have survived so far, which is exactly the reduced strip built left to right. Each new mark is compared against the survivor on top: if the two form a cancelling pair the survivor is popped, which is the same as erasing both and letting the strip close up, and otherwise the new mark is pushed. Marks the sweep has already pushed can still cancel later, because popping brings the mark beneath back to the top. The stack height at the end is the answer.

Pythonentry point: min_length

def min_length(s):
    # O(n) time, O(n) space. Sweep the strip once, keeping the marks that have
    # survived so far on a stack. A new mark either cancels with the survivor
    # on top of the stack, in which case that survivor is popped and the two
    # sides of the strip close up, or it becomes a survivor itself. What is left
    # on the stack at the end is exactly the strip that no longer holds a
    # cancelling pair, so its height is the answer.
    kept = []
    for mark in s:
        if kept and ((kept[-1] == 'R' and mark == 'B') or
                     (kept[-1] == 'G' and mark == 'Y')):
            kept.pop()
        else:
            kept.append(mark)
    return len(kept)

The obvious version

Erase every cancelling pair the string currently contains, then do it again on the shortened string, and keep going until a full round erases nothing. Report the length of what is left.

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_min_length(s):
    strip = s
    while True:
        shorter = strip.replace('RB', '').replace('GY', '')
        if shorter == strip:
            return len(strip)
        strip = shorter

How this problem was checked

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