The statement

A pair of charactor $$$(L, R)$$$ is called good or matched to each other if

• $$$L =$$$ '(' and $$$R =$$$ ')'
• $$$L =$$$ '[' and $$$R =$$$ ']'
• $$$L =$$$ '{' and $$$R =$$$ '}'

Notice that if $$$(L, R)$$$ is good then $$$(R, L)$$$ is not good

String can have many variation of categories, one of that is good string. Let a string $$$S$$$ of size $$$N$$$ is called good if

• $$$S$$$ is empty (its length $$$N = 0$$$)
• $$$S = S_1 + S_2 + \dots + S_n$$$. Where $$$S_i$$$ is a good string and + symbol mean that string concaternation
• $$$S = L + S_x + R$$$ where $$$S_x$$$ is a good string and $$$(L, R)$$$ is a good pair of charactor

Given a string $$$S$$$ of size $$$N$$$. We can add some charactor '(', ')', '[', ']', '{', '}' into anywhere in string $$$S$$$ but you cant replace or remove them. What is the minimum number of charactor need to add into string to make it good ?

The dynamic programming solution

Lets $$$F(l, r)$$$ is the answer for substring $$$S[l..r]$$$.

• If $$$l > r$$$ then the string is empty, hence the answer is $$$F(l, r) = 0$$$
• If $$$l = r$$$ then we should add one charactor to match $$$S_l$$$ to make this substring good, hence the answer is $$$F(l, r) = 1$$$
• If $$$S_l$$$ match $$$S_r$$$, the outside is already make a pair, so $$$F(l, r) = F(l + 1, r - 1) + 0$$$
• Else we can split into 2 other substring $$$S[l..r] = S[l..k] + S[k+1..r]$$$, for each $$$k$$$ we have $$$F(l, r) = F(l, k) + F(k+1, r)$$$ hence $$$F(l, r) = min(F(l, k) + F(k+1, r))$$$

///   Minimum number of error
/// = Minimum number of char need to add
int f[LIM][LIM]; /// Min error in substring s[l..r]
int solve(int l = 0, int r = n - 1)
{
    if (l > r) return 0; /// empty substring
    if (l == r) return 1; /// dont pair with other

    int &res = f[l][r];
    if (res != +INF) return res; /// calculated

    if (match(s[l], s[r])) /// paired up, no error
    {
        res = 0 + solve(l + 1, r - 1);
    }
    else
    {
        /// Split string into 2 halves
        /// s[l..r] = s[l..k] + s[k+1..r]
        /// f[l..r] = min(f[l..k] + f[k+1..r])
        for (int k = l; k < r; ++k)
        {
            minimize(res, solve(l, k) + solve(k + 1, r));
        }
    }

    return res;
}

///   Minimum number of error
/// = Minimum number of char need to add
int f[LIM][LIM]; /// Min error in substring s[l..r]
int solve()
{
    memset(f, 0, sizeof(f));
    for (int r = 0; r < n; ++r)
    {
        for (int l = r; l >= 0; --l)
        {
            f[l][r] = r - l + 1; /// Add one charactor to each one
            if (match(s[l], s[r])) /// Outside make a good pair of string
            {
                f[l][r] = f[l+1][r-1];
            }

            /// Split string into 2 halves
            /// s[l..r] = s[l..k] + s[k+1..r]
            /// f[l..r] = min(f[l..k] + f[k+1..r])
            for (int k = l; k < r; ++k)
            {
                minimize(f[l][r], f[l][k] + f[k+1][r]);
            }
        }
    }

    return f[0][n - 1];
}

Complexity:

• $$$F(l, r)$$$ have $$$O(n^2)$$$ states
• In each substring $$$S[l..r]$$$, we maybe to have a for-loop $$$O(n)$$$
• Hence the upper bound of the complexity is $$$O(n^3)$$$

My question

• If the string $$$S$$$ is consist of '(' and ')' then there is a $$$O(n)$$$ solution

int solve()
{
    int res = 0, diff = 0;
    for (char c : s)
    {
        diff += (c == '(') ? +1 : -1;
        if (diff < 0)
        {
            diff = 0;
            ++res;
        }
    }
    res += diff;

    return res;
}

• Can my algorithm improved into $$$O(n^2)$$$ or $$$O(n\ polylog(n))$$$ in somehow ?