企业官网建设流程全解析

Tk王国的括号

时间限制：1秒
空间限制：1024M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

众所周知，我们日常使用的括号如()、[]等，但是在遥远的 Tk 王国，他们使用字母作为括号。

具体地，Tk 王国共有 26 种不同的括号对，其中

• 前 13 对为"az"、"by"、"cx"、…、"lo"、"mn"（即小写字母表中的第i ii个字母和第27 − i 27-i27−i个字母，下标从 1 开始）；
• 后 13 对为"ZA"、"YB"、"XC"、…、"OL"、"NM"（即大写字母表中的第27 − j 27-j27−j个字母和第j jj个字母，下标从 1 开始）。

现在，给定一个长度为n nn的字符串s ss，字符串由大小写字母构成。你可以重复以下操作任意次：

• 如果存在长度为 2 的连续子串，且该子串正好是一对上述括号，则删除该子串。如果被删除的子串位于开头或结尾，则剩余部分直接形成新的字符串；否则，将被删除子串之前的部分和之后的部分拼接成新的字符串。

求经过若干次操作后，字符串可能达到的最短长度。

输入描述

第一行输入一个整数n ( 1 ≤ n ≤ 2 × 10 5 ) n\ (1 \le n \le 2 \times 10^5)n(1≤n≤2×105)，表示字符串长度；
第二行输入一个长度为n nn，仅由字母组成的字符串s ss。

输出描述

输出一个整数，表示字符串可以达到的最短长度。

示例1

输入：

5 azbyc

输出：

1

示例2

输入：

4 evPK

输出：

0

解题思路

本题是括号匹配消除问题，类似用栈处理相邻可配对字符。字符串由大小写字母组成，定义了 26 对特殊的括号对，每次可以删除相邻且恰好组成一对的两个字符，求经过任意次删除后字符串的最短长度。

1. 问题等价转化

• 给定字符集，某些二元组被视为可消除的“括号对”。
• 操作规则：不断寻找相邻的括号对并删除，删除后原不相邻的字符可能变成相邻，从而可能继续消除。
• 这一过程与“括号匹配”完全一致，可使用栈来模拟：遍历字符串，当前字符若能与栈顶字符组成一对括号，则弹出栈顶（消除这对括号）；否则将当前字符压入栈。
• 最终栈中剩余的字符即为无法再消除的部分，其长度就是答案。

2. 配对规则

• 小写字母对：前 13 对为"az","by","cx", …,"mn"。即对于小写字母a aa和b bb（a < b a < ba<b），若它们的字母表下标之和为 25（0‑based），则它们是一对。
• 大写字母对：后 13 对为"ZA","YB","XC", …,"NM"。即对于大写字母a aa和b bb（a > b a > ba>b），若它们的字母表下标之和为 25，则它们是一对。
• 判断函数match(a,b)根据大小写和下标和判断。

3. 算法步骤

1. 读入字符串长度n nn（可忽略）和字符串s ss。
2. 初始化一个空栈t（可用字符串模拟）。
3. 遍历字符串s ss中的每个字符c：
   • 若栈不为空且match(栈顶字符, c)为真，则弹出栈顶；
   • 否则将c压入栈。
4. 输出栈中剩余字符的个数，即为最短长度。

4. 复杂度分析

• 时间复杂度：每个字符至多入栈、出栈一次，总复杂度O ( n ) O(n)O(n)，n ≤ 2 × 10 5 n \le 2 \times 10^5n≤2×105，完全可行。
• 空间复杂度：O ( n ) O(n)O(n)，用于存储栈。

总结

本题实质是括号消除，利用栈的后进先出特性处理相邻配对。配对规则可通过字母下标之和为 25 且大小写方向固定来统一判断。算法简洁高效，只需一次线性扫描。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;boolmatch(chara,charb){if(islower(a))returna<b&&(a-'a')+(b-'a')==25;returna>b&&(a-'A')+(b-'A')==25;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);string s,t;cin>>s>>s;for(charc:s){if(t.size()&&match(t.back(),c))t.pop_back();elset.push_back(c);}cout<<t.size()<<endl;return0;}