swap する可能性のある \(2\) 文字の組み合わせとしては，以下だけを考えればよいです．

• )(
• )o
• )x
• o(
• x(

これ以外の swap を行うような最適解があった場合でも，それをうまく変形すれば上記の swap のみで損しない解が得られることがわかります．（詳細はただの場合分けなので省略します）

\(S\) の中で ( と ) だけを取り出して考えてみます． こうして得た文字列も当然括弧の対応が取れている必要があります．この文字列を最小コストで括弧の対応が取れているようにすることを考えると，その最終状態は一意です． この最終状態を \(T\) とおきます． この時，元の文字列での任意の最適解を考え，その終状態の (,) のみを取り出すと，それが \(T\) に一致することがわかります． これは，”余計”な )( の swap をすべてなくした解でも条件が達成されることから従います．

そこでまず，(, ) だけで括弧の対応が取れるように操作を行うことを考えます． この時，o,x との位置関係で，最終的な状態に自由度があります．

例えば，)ox( の場合では，ox() とするか，()ox とするかを選ぶことができます． これは一般には，次のようにまとめられます．

\(T\) を先頭から見たときに，( と ) の個数が一致する箇所を”谷”と呼ぶことにします． また，各 o および x について，その高さを，\((\) それより前に登場する ( の個数 - それより前に登場する ) の個数 \()\) と定義します． 元から高さが \(1\) 以上の o,x は無視して考えることにします． すると，各 o,x について，ある区間 \([l,r]\) が存在して，\(T\) の中で \([l,r]\) 番目のどこかの谷にその o or x がある，という状態になります． なお，o,x 同士の swap がないことから，それらの前後関係も保持されている必要があります． また， ox が関わる swap では必ずその高さが \(1\) 増えることと，それらの高さが最終的に \(0\) であることから，操作回数の合計は一定です．

例えば，\(S=\))x)o(x( のとき，\(T=\)()() であり，谷は \(3\) つあります． それぞれの o,x がある場所は，以下で☆で示した場所のどこかです．

• 最初の x: ☆()☆()
• o: ☆()☆()☆
• 最後の x: ()☆()☆

) \(+(\) o,x からなる列\()+\)( という部分について考えます． ここで，真ん中の部分の x を高さ \(1\) 以上にするためには，端にある) と ( を移動させる必要があります． ここで，真ん中にある o の連続する部分だけコストが減ると考えてみることにします．

ここまでくればDPができます． \(dp[i][j]=i\) 番目の谷までで \(j\) 番目までの ox を使用したときの最小コスト，とすればよいです． なお，最初の谷と最後の谷ではコストの形が他と少し異なるため注意が必要です． このDPは \(O(|S|^2)\) で動作し，十分高速です．