Suppose, $\alpha_1, … , \alpha_n \in \{(, )\}^*$ are arbitrary bracket sequences with total length $\sum_{i=1}^n |\alpha_i| = N$.
Can we check in polynomial (in respect to $N$) time whether a Dyck word can be assembled from those fragments (that is, does there exist $\sigma \in S_n$, such that $\alpha_{\sigma(1)}…\alpha_{\sigma(n)}$ is a Dyck word — a word satisfying the formal grammar $S \to (S)S|\Lambda$)?
Note, that this problem is NP. Indeed, if we obtain a valid $\sigma$, its validity can be checked in linear time.
The naive approach of checking all possible $\sigma$ has time complexity $O(n (n!)) = O(e^{n \log n - n + \frac{2}{3}\log n})$. However, it is very likely, that there is some other significantly faster way to solve this problem…
Define the weight of a substring as the number of $($ minus the number of $)$.
First check if the total weight of the strings is $0$.
For each string check the minimum weight of a prefix, and call this the risk of the string.
The following greedy algorithm will produce a dyck path if one exists:
Let $sum$ be the total value of the current words.
Select the string $s_i$ with risk greater than or equal to sum that has the highest weight and place it at the end.