0003EasyStringStack

Template Grouping Check

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.

A template compiler scans a source file, discards every character that is not a grouping mark, and keeps what remains in order as the string code. So code is built only from round marks ( and ), square marks [ and ], and curly marks { and }. The compiler only runs this check on files that contained at least one grouping mark.

The compiler calls the grouping sound when the marks can be paired off so that all of the following hold:

Every mark belongs to exactly one pair.
In each pair, an opener comes first and a closer of the same shape comes later.
No two pairs cross: for any two pairs, one is either entirely inside the other or entirely outside it.

Return true when the grouping in code is sound, and false when no such pairing exists.

Examples

Example 1

Input: code = "([]{})"
Output: true

The square pair and the curly pair both sit entirely inside the round pair, so nothing crosses and every mark is used exactly once.

Example 2

Input: code = "{(})"
Output: false

Pairing the round marks and the curly marks here forces the two pairs to cross, and no other pairing is available.

Example 3

Input: code = "[[]"
Output: false

There are three marks, an odd count, so at least one cannot belong to a pair.

Example 4

Input: code = "]"
Output: false

A single closer has no opener before it to pair with.

Constraints

1 <= code.length <= 10^4
`code` contains only the six characters `(`, `)`, `[`, `]`, `{`, `}`

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 is_balanced(code: str) -> bool:

Java

public boolean isBalanced(String code)

The intended approach

Time O(n)Space O(n)

The group that a closer must shut is always the newest one still waiting, which is exactly last-in-first-out behaviour, so a stack of pending openers is enough. Push every opener; on a closer, pop and confirm the shape agrees, failing immediately if the stack is empty or the shapes differ. The string is sound only if the stack is empty once the scan finishes.

Pythonentry point: is_balanced

def is_balanced(code):
    partner = {')': '(', ']': '[', '}': '{'}
    pending = []
    for mark in code:
        if mark in partner:
            if not pending or pending.pop() != partner[mark]:
                return False
        else:
            pending.append(mark)
    return not pending

The obvious version

Repeatedly delete adjacent matched pairs until nothing changes; sound iff the string empties. No stack.

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_balanced(code):
    s = code
    while True:
        for p in ("()", "[]", "{}"):
            if p in s:
                s = s.replace(p, "")
                break
        else:
            return s == ""

How this problem was checked

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