Abstract / Summary

Check if a string of parentheses with stars can be made valid by replacing stars appropriately.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 45% (300k+ submissions).

Typical patterns to solve this problem:

• Greedy
• Stack
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether a parenthesis string s can be transformed into a balanced sequence when some positions are locked (cannot be changed) and others are unlocked (free to become either '(' or ')'). The algorithm proceeds in three logical phases: an initial length parity check, a forward scan that enforces a minimum count of opening brackets, and a backward scan that enforces a minimum count of closing brackets. Each phase is implemented with concise Python constructs that avoid unnecessary allocations and allow early termination when a violation is detected.

Length Parity Check

The very first operation discards any input whose length is odd, because a balanced parenthesis string must contain an even number of characters. The check uses a bitwise AND to test the least-significant bit, which is a constant-time operation.

if len(s) & 1:
    return False

By rejecting odd-length inputs immediately, the function avoids all further processing for cases that can never succeed, saving work for large inputs.

Forward Scan - Ensuring Sufficient Opens

The forward pass walks through the string from left to right while maintaining a counter called depth. The counter represents the net number of opening brackets that can be placed up to the current position, assuming unlocked positions are optimistically treated as '('.

For each character c and its lock status l:

• If the position is unlocked (l == "0"), the algorithm pretends the character is '(' and increments depth.
• If the position is locked and the character is '(', depth is also incremented.
• Otherwise (locked ')'), depth is decremented.

If at any point depth drops below zero, there are more closing brackets than can be matched by preceding opens, even after exploiting all unlocked positions. The function returns False immediately.

depth = 0
for c, l in zip(s, locked):
    if l == "0" or c == "(":
        depth += 1
    else:
        depth -= 1
        if depth < 0:
            return False

This scan guarantees that, from the start up to any index, the number of potential opens never falls short of the required closes.

Backward Scan - Ensuring Sufficient Closes

The second pass mirrors the first but traverses the string in reverse order. Here the algorithm treats unlocked positions as if they were ')', thereby counting potential closing brackets. The same depth variable is reused, starting from zero.

During the reverse iteration:

• If the position is unlocked (l == "0") or the locked character is ')', depth is incremented.
• Otherwise (locked '('), depth is decremented.

A negative depth indicates that, from the end toward the current point, there are more opening brackets than can be matched by subsequent closes, even after using all unlocked slots as closes. The function aborts with False in that case.

depth = 0
for c, l in zip(reversed(s), reversed(locked)):
    if l == "0" or c == ")":
        depth += 1
    else:
        depth -= 1
        if depth < 0:
            return False

By confirming the reverse condition, the algorithm ensures that the string can be balanced from both ends, which is necessary because unlocked characters can be assigned flexibly.

Final Decision

If both scans complete without triggering a negative depth, the function concludes that a valid assignment of unlocked characters exists and returns True.

return True

Edge Cases Handled

The code explicitly addresses several subtle scenarios:

• Odd length inputs are rejected instantly, covering the case where a balanced string is mathematically impossible.
• All positions unlocked: the forward pass treats every character as '(', while the backward pass treats every character as ')'. The two passes together verify that a perfect pairing can be arranged.
• All positions locked: the algorithm behaves exactly like a standard parentheses validator, because the unlocked-branch of each conditional never activates.
• Mixed locked and unlocked characters: the forward pass assumes unlocked characters contribute positively to the opening count, while the backward pass assumes they contribute positively to the closing count. This dual assumption captures the flexibility of unlocked slots without enumerating all assignments.
• Early violation detection: if a prefix cannot possibly be balanced, the function exits before scanning the remainder, which is crucial for long strings where the imbalance occurs early.

Performance Optimizations

The implementation exhibits several efficiency-focused choices:

• The parity test uses a bitwise operation, which is marginally faster than a modulo operation.
• Both scans are single passes over the input, each using zip (or zip with reversed) to iterate without constructing intermediate lists.
• The use of reversed on the original strings avoids copying data; Python’s iterator protocol yields characters on demand.
• Early returns on the first detection of an impossible condition prevent unnecessary work, especially beneficial for large inputs with early mismatches.
• The reuse of the depth variable eliminates the need for additional state containers.

Collectively, these decisions keep the runtime proportional to the length of the input while maintaining a low memory footprint, making the solution well-suited for high-volume or real-time processing contexts.

Imagine a long train track where the train cars are either opening brackets or closing brackets. Some cars are locked in place, while others are special and can be turned into either kind. A balanced set of brackets is like a perfect dance where every person who reaches out a hand to open a circle finds someone else to close it.

The very first rule checks if there is an odd number of train cars. If there is, it is impossible for everyone to have a partner, so the set cannot be balanced.

Next, the code walks from the beginning to the end of the train, pretending every flexible car is an opening bracket. It counts how many opening brackets exist versus closing ones. If at any point there are more closing brackets than opening ones, the dance falls apart because someone is trying to close a circle that has not started yet.

After finishing the first walk, the code turns around and starts from the back. This time, it pretends every flexible car is a closing bracket. By traveling backward, it ensures that every opening bracket has a closing partner waiting for it. If the count ever drops below zero during this journey, the brackets are mismatched.

If the train passes both of these checks, it means there is a way to set every flexible bracket so that all the opening and closing pairs match up perfectly.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python				TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java		Python			Go	TS
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem				Ruby
	fsq	C++
	JoshCrozier		JS
	lkwq007					Python
	Shamik07						Dart
	suxrobGM							C#
	varunu28			Java
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
suxrobGM	C#
varunu28	Java
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality