SPyofgame's blog

Minimum number of charactor need to add to make a valid barrack string
By SPyofgame, history, 4 years ago, In English

The full statement

Main statement

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

  • $$$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.

The question is that: What is the minimum number of charactor need to add into string to make it good ?

Limitation: $$$N = |S| \leq 500$$$

The dynamic programming solution $$$O(n^3)$$$

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$$$
  • 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))$$$
  • Notice that when $$$S_l$$$ match $$$S_r$$$, $$$F(l, r) = min(F(l + 1, r - 1), min(F(l, k) + F(k+1, r)))$$$

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)$$$
Recursive Code
Iterative Code
Full Code

The other dynamic programming solution $$$O(n^3)$$$

Base cases:

  • If $$$l > r$$$ then the string is empty, hence $$$F(l, r) = 0$$$
  • If $$$l = r$$$ then we should add one charactor to match $$$S_l$$$ to make this substring good, hence $$$F(l, r) = 1$$$

Branch and bound cases:

  • If $$$S_l$$$ is close barrack, then add a open barrack before it, hence $$$F(l, r) = F(l + 1, r) + 1$$$
  • If $$$S_r$$$ is open barrack, then add a close barrack after it, hence $$$F(l, r) = F(l, r - 1) + 1$$$
  • If $$$(S_l, S_{l+1})$$$ is good, then just paired it up, hence $$$F(l, r) = F(l + 2, r) + 0$$$
  • If $$$(S_{r-1}, S_r)$$$ is good, then just paired it up, hence $$$F(l, r) = F(l, r - 2) + 0$$$

Main cases:

For each $$$k = l \rightarrow r - 1$$$

  • If $$$S_k$$$ match $$$S_r$$$, minimize $$$F(l, r)$$$ with $$$F(l, k - 1) + 0 + F(k + 1, r - 1)$$$
  • Else add a open charactor at k to match $$$S_r$$$, minimize $$$F(l, r)$$$ with $$$F(l, k) + 1 + F(k + 1, r - 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)$$$ or $$$O(1)$$$ for transistion
  • Hence the upper bound complexity is $$$O(n^3)$$$
  • Hence the lower bound complexity is $$$O(n^2)$$$
Recursive Code
Full code
Optimize version

My question

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

  • Can my algorithm ($$$dp[l][r] = min(dp[l][k] + dp[k + 1][r])$$$) improved into $$$O(n^2\ polylog)$$$ or lower in somehow ?

  • Failed to use Knuth algorithm $$$(dp[l][r] = min(dp[l][k] + dp[k][r] + cost[l][r])$$$ since fully-motone condition is not satisfied

  • Vote: I like it
  • +40
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you SPyofgame

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Nice blog, nii-chan <3

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can’t you solve the 3 types of bracket sub sequences independently from each other. Let's say string is not good because type1 characters are missing. Then we can only fix it by adding type1 characters at appropriate places and will not effect type 2 or type 3 characters in any way. Did you try this way?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    {(}) in this case, the answer is 2.

    While doing like your way, the answer is only 0

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Ok I understand. It's not a regular bracket sequence. It's can only have nested strings or concatenation of nested strings.

      → Reply