M  Deformed Balance

In what follows, we write an open parenthesis as L and a close parenthesis as R. The BNF formulation of the deformed strings can be defined as follows.

Consider a slightly modified version of \(E\), where the terminal symbol L is replaced by either ‘{’ or ‘}’:

Suppose that a string \(S'\) conforms to \(E'\). The following can be proven by induction.

• The string \(S'\) contains an odd number of R’s.
• Removing R from \(S'\) will result in a balanced sequence consisting of ‘{’ and ‘}’.
• Two terminals ‘{’ and ‘}’ do not appear at adjacent positions; at least one R is always between them.
• The appearance of one terminal R flips the direction (opening or closing) of brackets {}.

Thus, \(S'\) has a form {{{ ... {{{ R }}} ... }}} R {{{ ... }}} R }}} ... }}} R {{{ ... {{{ R }}} .... Two or more R’s may appear contiguously. Conversely, if a string \(S'\) has this form and the brackets {} are balanced, we can generate \(S'\) using \(E'\):

• R at odd occurrences should be generated by the first rule,
• R at even occurrences should be generated by the second, and
• each pair of corresponding ‘{’ and ‘}’ should be generated by the third.

Hence, if we want to determine whether a string consisting of R and L conforms to \(E\), we can do so by replacing the L’s with either ‘{’ or ‘}’ and then checking if that conforms to \(E'\).

For determining whether a string \(W\) has a deformed balance or not, we track two values \(x\) and \(y\) from the beginning, where \(x\) is the current nesting level for the parentheses LR, and \(y\) is the nesting level for the brackets {}. During the tracking \(x, y \ge 0\) must be always hold. At the end of the string, \((x, y) = (1, 0)\) must hold for the string \(W\) to have a deformed balance.

The values of \((x, y)\) change as follows:

• if the next character is L,
  • \((x + 1, y + 1)\) if \(x + y = 0 \pmod{2}\), or
  • \((x + 1, y - 1)\) otherwise
• if the next character is R, \((x - 1, y)\).

Now, let’s move on to the original problem. For the input string \(S\), we can prepend and append some characters to \(S\) to form \(S' = X + S + Y\).

• The concatenation \(X + S\) should result in a state \((x', y')\) such that \(x', y' \ge 0\).
  • After this, if \(x' = 0\) and \(y' = 0 \pmod{2}\), \(|Y| = 3 + 2y'\) is the shortest possible for \(S'\) to have a deformed balance.
  • Otherwise, \(|Y| = x' + 2y' - 1\) is the required minimum.
• The only forms of \(X\) that need to be considered are one of the following:
  • LLL... LLL
  • LLL... LLL R LLL... LLL
  • LLL... LLL R LLL... LLL R
• Note that we don’t need to consider a form like LLLRLLLRLL because the last L’s can be moved to the first part: LLLLLRLLLR is enough to consider.
• For the third case above, suppose that \(X\) has a form \(L^f R L^g R\) for some \(f \gt 0\) and \(g \ge 0\) (with \(f + g \ge 2\)). The state after reading \(X\) is \((f + g - 2, f - g)\). For \(S'\) to have a deformed balance, \(f + g - 2 + a \ge 0\) and \(f - g + b \ge 0\) must hold, where \(a\) and \(b\) are constants that can be deduced from the input.
• The length of \(Y\) is \(|Y| = (f + g - 2 + c) + 2(f - g + d) - 1\) for some \(c\) and \(d\) (unless \(X + S\) ends up in the state \((0, 2y'')\) for some \(y'' \ge 0\).)
• Thus, the total added length is \(|X| + |Y| = 4f + (\text{const.})\). To find the answer, it suffices to iterate \(f = 1, 2, \ldots\) and find the minimum \(f\) such that there exists \(g\) satisfying all the conditions above.
• The same arguments hold for the other cases. Note that the constants \((a, b, c, d)\) may vary in the second and the third cases, due to the flip of brackets {}.

Total time complexity is \(O(n)\).