Show problems as
Classic problem #2696EasyStringStackSimulation

Minimum String Length After Removing Substrings

Real-world version: Cancelling Paint Marks
Tracked in this browser only
Read Minimum String Length After Removing Substrings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_length(s: str) -> int:
Java
public int minLength(String s)

More on the same topics