Skip to content

Longest Balanced Subsequence

01 · Question

Given a string containing only parentheses, return any longest balanced subsequence. You may delete characters anywhere but must preserve the order of retained characters. Equivalently, delete as few parentheses as possible to make the result balanced.

Examples: ))(())(() → (())(); ())(() → ()(); ( → ""; an empty input returns "". Multiple optimal results may be valid.

02 · Analysis

Keep a stack of unmatched opening indices. Pair a closer with the newest available opener; if none exists, mark that closer for deletion. After the scan, mark every opening still on the stack. Rebuild the string without marked indices.

For ())((), index 2 is an unmatched closer and index 3 remains an unmatched opener; skipping them gives ()().

Optimality: an unmatched closer has no earlier unused opener, and the final surplus openings have no later unused closers. Greedy matching maximizes the number of pairs, so no solution can retain more characters. O(n) time and O(n) space, including the reconstructed output. Do not return early on the first unmatched closer: later characters may still form valid pairs.

03 · Solution

Reference solution

1def longest_balanced_subsequence(s):
2    openings = []
3    remove = set()
4    for index, char in enumerate(s):
5        if char == '(':
6            openings.append(index)
7        elif openings:
8            openings.pop()
9        else:
10            remove.add(index)
11    remove.update(openings)
12    return ''.join(char for index, char in enumerate(s) if index not in remove)
Previous
Custom Brackets
Next
Min Stack