Balanced Partition

01 · Question

Given a balanced string containing only parentheses, return the maximum number of nonempty balanced substrings into which the entire string can be partitioned.

Examples: (())()(()()) → 3, with pieces (()) | () | (()()); ((())) → 1; ()() → 2; the empty string gives 0.

02 · Analysis

Track height, adding one for each opener and subtracting one for each closer. Count every return to zero after consuming a character.

Why optimal: a balanced piece must end at the same height at which it began. All preceding pieces are balanced, so every legal cut has global height zero. Cutting at every such boundary is feasible and includes every possible cut. O(n) time, O(1) extra space. The input guarantee matters: a return to zero after a negative prefix is not a balanced piece.

03 · Solution

Reference solution

1def max_balanced_partition(s):
2    height = pieces = 0
3    for char in s:
4        height += 1 if char == '(' else -1
5        if height == 0:
6            pieces += 1
7    return pieces

Current URL with Forward

Custom Brackets