7
$\begingroup$

I call a string of brackets 'correct' if every opening bracket has a corresponding closing bracket somewhere after it and every closing bracket has a corresponding opening bracket somewhere before it. For example

(())()((()()))

is a correct string and

)()()(

is an incorrect string.

An operation consists of taking a contiguous subsequence of the input string and 'flipping' every bracket in that subsequence.

Given an arbitrary string of brackets (of even length), the task is to find the smallest number of such operations needed to change it to a 'correct' string of brackets.

Another way to look at this problem is to have a string of +1s and -1s, and to try to find the smallest number of operations (of multiplying every number on an interval by -1) needed to make every prefix of this string nonnegative and every suffix nonpositive.

$\endgroup$
  • $\begingroup$ Can you credit the source where you encountered this problem? $\endgroup$ – D.W. Jan 22 '20 at 16:58
  • $\begingroup$ It's something that I came up with in the shower, I haven't seen any source for this problem, but it's similar to some problems from olympiads in informatics (notably, i've seen one with a similar premise, but the operations were limited to changing a single character, which makes it considerably easier). I've tried dynamic programming with respect to where the last operation has ended (in O(n^2) time and memory), but so far no luck $\endgroup$ – Voso Jan 22 '20 at 18:15
  • 1
    $\begingroup$ Have you tried to compute, for each $i$ and $j$, the minimum number of changes needed to make the prefix of length $i$ sum to exactly $j$ (possibly $\infty$)? $\endgroup$ – Yuval Filmus Jan 22 '20 at 19:53
  • $\begingroup$ No! But I see how it could solve this problem. If for every i and j we kept two values, one corresponding to the answer if we allow the latest change to end on position i and the second one corresponding to the answer if we don't, then we can always deduce the states from previous ones. $\endgroup$ – Voso Jan 22 '20 at 22:44
4
$\begingroup$

The DP suggested in the comments by Yuval Filmus indeed works: we can solve the problem in $\mathcal{O}(n^{2})$ by DP.

First note that we may assume that intervals are not allowed to overlap. Take any two overlapping intervals $[a, b)$ and $[c, d)$. WLOG $a \leq c$. Then we can replace the two intervals with the intervals $[a, c)$ and $[\min(b, d), \max(b, d))$ that do not overlap, have shorter total length and cover exactly the same elements.

Replace opening brackets with $1$, closing brackets with $-1$. Now the problem corresponds to applying the minimum number of operations "multiply interval by $-1$" such that every prefix has nonnegative sum, and the sum over the entire array is zero.

We construct a solution left-to-right. At every position we can either start an interval, or end an active interval.

Let $DP[m][s][0]$ denote the minimum number of intervals we need to use such that every prefix sum in the first $m$ elements is nonnegative, the sum of the first $m$ elements is $s$, and we do not have an active interval. Similarly $DP[m][s][1]$ is the same value where we do have an active interval.

If the $m$th value is $1$, for $0 \leq s \leq m$ we set

  • $DP[m][s][0] = DP[m-1][s-1][0]$
  • $DP[m][s][1] = DP[m-1][s+1][1]$

Otherwise we set

  • $DP[m][s][0] = DP[m-1][s+1][0]$
  • $DP[m][s][1] = DP[m-1][s-1][1]$.

Then we end and start intervals, setting

  • $DP[m][s][0] = \min(DP[m][s][0], DP[m][s][1])$
  • $DP[m][s][1] = \min(DP[m][s][1], DP[m][s][0] + 1)$

The base case is $DP[0][0][0] = 0$, $DP[0][0][1] = 1$.

There are $\mathcal{O}(n^{2})$ states, and we do $\mathcal{O}(1)$ work to calculate each of them, therefore the algorithm runs in $\mathcal{O}(n^{2})$. The DP can be implemented to use $\mathcal{O}(n)$ memory by only storing the values of $DP$ for the current $m$.

Here is a C++ implementation of the algorithm.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}
$\endgroup$
0
$\begingroup$

Nice question!

Here is the problem in more popular terms.

Balanced Parentheses

A string of parentheses is balanced if we can change it to the empty string by removing substrings "()" repeatedly. For example, empty string, "()" and "(())()((()()))" are balanced but none of "())" and ")()()(" is balanced.

It is clear that a balanced string must start with "(" and ending with ")". It must be of even length as well.

the Problem of Minimum Operations to Balance a String

Let s be a non-empty string of parentheses of length n. The only operation we can perform is flipping every parenthesis in a substring, that is, changing every "(" to ")" and every ")" to "(" for some contiguous characters in the string. The problem is how to find the smallest number of operations that make s balanced.

an Approach by Dynamic Programming

What are the appropriate subproblems? They are dp[i][j] for 0 <= i < j < n, where dp[i][j] is the minimum number of operations that balance the substring between indice i and index j inclusive. The wanted minimum number of operations that balance s is dp[0][n-1].

Since any string of odd length cannot be balanced, we will restrict our attention to strings of even length from now on.

the base cases dp[i][i+1] is 0 if the substring between i and i+1 is balanced, i.e, "()". It is 1 otherwise.

the recurrence relation I will use Java to define the recurrence relation.

void dp(int i, int j) {
    assert 0 <=i && i + 2 < j && j <= L;

    int min = dp[i + 1][j - 1];
    if (s.charAt(i) == ')' && s.charAt(i + 1) == '(') min++;
    if (s.charAt(j) == '(' && s.charAt(j - 1) == ')') min++;

    for (int k = i + 1; k < j - 1; k+=2) {
        if (a[k] == 1 && a[k + 1] == -1) {
            if (min > dp[i][k] + dp[k + 1][j] - 1) {
                min = dp[i][k] + dp[k + 1][j] - 1;
            }
        } else {
            if (min > dp[i][k] + dp[k + 1][j]) {
                min = dp[i][k] + dp[k + 1][j];
            }
        }
    }

    dp[i][j] = min;
}

The recurrence relation comes from the following well-known property of balanced strings. A non-empty string is balanced if and only if it is the concatenation of two balanced strings or "(" followed by a balanced string followed by ")".

The processing before the for loop, which sets min to be dp[i + 1][j - 1] plus 0, 1 or 2, comes from the fact that "(" followed by a balanced string followed by ")" must be a balanced string.

The processing in the for loop, which tries to shrink min to dp[i][k] + dp[k + 1][j] minus 0 or 1 for some k that is between i and j, comes from the fact that the concatenation of two balanced strings must be a balanced string.

The time-complexity of this approach is $O(n^3)$. The space-complexity is $O(n^2)$.

Length of the "most unbalanced" strings

The smallest length of a string that cannot be balanced by less than 2 operations is 4. For example, ")((("

The smallest length of a string that cannot be balanced by less than 3 operations is 10. For example, ")(((((())("

The smallest length of a string that cannot be balanced by less than 4 operations is 22. For example, ")(())))(((((((((((())(".

Question: What is the smallest length of a string that needs at least 5 operations? As I have computed, it must be greater than 28. However, my computation is not enough to determine the actual value. How fast can we compute these smallest lengths?

$\endgroup$
  • $\begingroup$ It looks like the smallest length of a string that needs at least 5 operations is 46. In general, here is my most unbalanced string conjecture for $k\ge1$: every string of parentheses of even length shorter than $3*2^k−2$ can be balanced with $k$ operations. Furthermore, there are exactly two strings of that length that cannot be balanced with $k$ operations. For $k=4$, one such string is 1 ")", 2 "("s, 4 ")"s, 8 "("s, 16 "("s, 32 ")"s, 16 ")"s, 8 "("s, 4 ")"s, 2"("s, 1"(". Flipping the 32 ")"s in the middle will get the other string. The cases with $k\neq4$ are similar. $\endgroup$ – John L. Jan 26 '20 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.