#588. 【2025-11-26】# T1 修复括号串 (repair,1s,512MB) - 文件读写

【2025-11-26】# T1 修复括号串 (repair,1s,512MB) - 文件读写

T1 修复括号串 (repair,1s,512MB)

题目描述

给定一个长度为 nn ( nn 为偶数),由左右括号组成的字符串 SS 。

每次操作可以修改 SS 中的某个字符,求出最少的操作次数,使 SS 变成一个括号串。

我们定义满足以下条件的字符串为括号串。

1.空串是括号串。

2.如果 AA 是括号串,(A)(A) 是括号串。

3.如果 A,BA,B 都是括号串,ABAB 是括号串。

输入格式

第一行输入一个整数 nn 。

第二行输入一个长度为 nn 的字符串 SS ,SS 中每个字符为左括号或者右括号。

输出格式

输出一行一个整数,表示最少的操作次数。

输入输出样例 #1

输入 #1

4
())(

输出 #1

2

输入输出样例 #2

输入 #2

2
((

输出 #2

1

说明/提示

对于 30%30\% 的数据, n≤10n \le 10 。

对于另外 30%30\% 的数据,n≤103n \le 10^3 。

对于另外 20%20\% 的数据,SS 中仅包含左括号。

对于全部数据, 1≤n≤1061 \le n \le 10^6 , nn 是偶数,SS 长度为 nn ,而且每个字符为左括号或者右括号。