Finding longest balanced parentheses using $n$ smaller strings

Question

Given $n$ strings consisting only of '$($' and '$)$', how one can compute the length of the longest string that can be built by concatenating a subset of these strings in some order such that the resulting string is a balanced parenthesis?

Example: If we have the strings $\{"(()",")(",")","(("\}$, one can build the string $"(())()"$ which has length 6. We cannot construct a longer one from the previous set, thus the answer is 6.

In general, the answer is always even, and always $\geq 0$ because we can always take the empty set.

Problem source: North American Invitational Programming Contest (NAPIC) 2017, Problem A.

Answer 1

First, let's remark that the order in which you put the selected strings is not significant as long as it is valid. That means that you can put the strings in a canonical order and you know that the solution is a subsequence of that sequence. The canonical order I suggest is first the strings which increase the number of opened parenthesis (with D.W. triplet notation, the triplets $\langle i,j,\ell \rangle$ for which $j>i$) tied resolved by increasing $i$, then those which don't change the number of opened parenthesis ($i=j$) then those which decrease the number of opened parenthesis($i>j$) this time solving the tie by decreasing $i$.

Then you apply the favorite technique of programming contests: dynamic programming. You are filling an array of $n$ columns. An entry $c,r$ of $\ell$ states that with the $c$ first strings in our canonical order, you can have $r$ opened parenthesis pending with a total length of $\ell$. This is filled using the content of the column $c-1$ with the initial column stating that with no strings you have a $0$ opened parenthesis pending and a length of $0$. You have to pay attention to avoid entries which would need to have more opened parenthesis than available, and when an entry is reachable with two lengths to keep the longest one.

You avoid the exponential behavior because you know that the strings have a bounded length of 300 (thus you can't have more than $300\; c$ opened parenthesis after $c$ columns instead of the $2^c$ entries which would have been possible without that bound) and thus you are sure that after the ninth or so column, you'll have duplicate entries.

Answer 2

I don't know of any algorithm whose worst-case running time is reasonable. I list below an approach that almost works, but becomes slow when we add logic to ensure that no string is used more than once. Perhaps you can find a way to improve it.

Treat two strings $x,y$ as equivalent (written $x \sim y$) if you can obtain one from the other by repeatedly removing or inserting $()$. For instance, $()( \sim ( \sim (()$.

Now, every string of parenthesis is either (a) equivalent to $)^i (^j$ for some $i,j \in \mathbb{N}$, or (b) cannot appear as a substring of any string with balanced parentheses. In case (b), there's no way to extend it to a solution to the problem, so such strings can be ignored, and we can focus on case (a).

We'll identify each string of parentheses with the tuple $\langle i,j,\ell \rangle$, where the string is equivalent to $)^i (^j$ and $\ell$ is the length of the string. Build an (implicitly-represented) graph corresponds to all valid sequences. We'll basically do pruned search in this graph.

In particular, we'll imagine a graph with one vertex for each valid sequence, and with the edge $u \to v$ if the sequence $v$ can be obtained from $u$ by appending one of the $n$ strings to $u$. Now, you can search the graph to find all vertices that are reachable from $\epsilon$ (the empty sequence of length 0). We're looking for the longest configuration of the form $\langle 0,0,\ell \rangle$ (i.e., the one where $\ell$ is as large as possible).

You can use any graph reachability algorithm, such as BFS. However as a heuristic I would suggest prioritizing exploration of longer configurations first, e.g., using a priority queue that is keyed on $\ell$. (Equivalently, you can think of this as using Dijkstra's algorithm where the length of each edge is the number of symbols appended -- the amount that it increases the length of the sequence.)

The problem with this approach is that it might end up using some of the $n$ strings more than once. Here is one way to fix that: now a configuration is given by $\langle i,j,\ell,S \rangle$, where $S$ represents the subset of $n$ strings that were used to construct this string. Unfortunately, now there can be exponentially many configurations.

A possible advantage of this approach is that you don't try to explore all orderings: you can prune sequences can't possibly be present in any valid answer, and thus possibly explore fewer than all possible subsets and orders. That said, this could still take exponential time in the worst case, so it might fail to be feasible.

This approach is asymptotically slightly better than the brute-force approach of exhaustively trying all possible sequences. The brute-force algorithm takes $O(n!) = O(2^{n \log n + O(n)})$ time. The approach I list here takes $O(n^3 2^n) = O(2^{n + O(\lg n)})$ time, which is better... but still exponential, alas.

Answer 3

Your problem is $\text{NP}$-hard. It is an optimization version of the following decision problem. \begin{array}{|l|} \hline \textbf{Decision problem }\mathcal{P}\textbf{:}\\ \text{Given }n\text{ strings consisting only of `(' and `)', does there exist a subset of strings}\\ \text{which when concatenated in some order yield a string with balanced parenthesis?}\\ \hline \end{array}

I will now prove that Problem $\mathcal{P}$ is $\text{NP}$-hard.

---

We reduce subset sum problem which is known to be $\text{NP}$-complete to Problem $\mathcal{P}$.

Subset Sum Problem [NP-Complete]: Let $S=\{a_1, \cdots, a_k\}$ be the finite set of (including negative) integers. We need to decide whether there exists a subset $R \subseteq S$ such that sum of elements in $R$ is zero.

Reduction to Problem $\mathcal{P}$: We encode all $a_i \in S$ to strings of parenthesis in the following manner.

• If $a_i = +m$, then its string encoding is $\text{Encode}(a_i) = `` \underbrace{((\cdots(}_{m \text{ times}} "$
• If $a_i = -m$, then its string encoding is $\text{Encode}(a_i) =`` \underbrace{))\cdots)}_{m \text{ times}} "$

Now we encode sum operation. Let $S' = \{a_1, a_2, \cdots a_q \} \subseteq S$ be any non-empty set such that $a_1 \geq a_2 \geq \cdots \geq a_q$. Then sum over $S'$, $\Sigma \ S' = \text{Encode}(a_1) \circ \text{Encode}(a_2) \circ \dots \circ \text{Encode}(a_q)$, where $\circ$ is a string concatenation operation. With this encoding, following invariant property holds: Sum of a value $(i-j)$ is encoded as a string of the form $`` (^i \ )^j "$. Thus, the sum is zero iff parenthesis are balanced.

You can convince yourself that this reduction is polynomial one. This proves NP-hardness of your optimization problem. One way you can solve your problem is by encoding it in SAT or Integer Linear Programs. Then you can use state of art solvers like Z3, LP_SOLVE or GLPK to get a solution.