小红的环形字符串时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿到了一个环形字符串。所谓环形字符串即首尾相连的字符串。小红每次可以删除两个相邻的相同字符。小红想知道最多可以删除多少个字符输入描述第一行输入一个正整数n nn代表环形字符串的长度。第二行输入一个长度为n nn且仅由小写字母组成的字符串。请注意该字符串是首尾相连的。1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105输出描述最多可以删除的字符数量。示例 1输入5 abcba输出4说明可以先删除两个 a字符串变成 bcb。然后删除两个 b字符串变成 c。总共删除了 4 个字符。数据范围1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105字符串仅由小写字母组成解题思路本题是栈模拟 环形消除的经典问题。给定一个环形字符串每次可以删除两个相邻且相同的字符删除后字符串会重新连接包括首尾相连要求最多能删除多少个字符。1. 问题等价转化对于线性字符串删除相邻相同字符的过程可以用栈模拟遍历字符若当前字符与栈顶相同则弹出栈顶相当于消除一对否则压入栈。最终栈中剩余字符无法再消除。但本题是环形字符串首尾字符也可能相邻并相同因此在线性消除后还需要检查栈的首尾是否相同。若相同可以继续消除直到栈首尾不同或栈为空/只剩一个字符。最终无法消除的字符数量就是栈的最终大小答案即为n − 栈大小 n - \text{栈大小}n−栈大小。2. 算法实现读入n nn和字符串s ss。使用双端队列dequechar模拟栈遍历字符串s ss的每个字符c cc若队列非空且队尾字符等于c cc则弹出队尾消除一对否则将c cc压入队尾。处理环形首尾当队列大小大于 1 且队首字符等于队尾字符时同时弹出队首和队尾消除一对重复此过程直到条件不满足。输出n - q.size()即最多删除的字符数。3. 复杂度分析时间复杂度每个字符最多入队、出队一次首尾消除操作总次数不超过n / 2 n/2n/2总时间复杂度O ( n ) O(n)O(n)。n ≤ 10 5 n \le 10^5n≤105非常快。空间复杂度双端队列最多存储n nn个字符空间复杂度O ( n ) O(n)O(n)。总结利用栈在线性消除相邻相同字符再通过双端队列处理环形首尾可能存在的消除。核心在于理解环形结构使得首尾字符也可能相邻因此需要在一次线性消除后继续检查首尾。该方法简洁高效完美解决了环形字符串的消除问题。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod998244353;voidsolve(){ll n;cinn;string s;cins;dequecharq;for(autoc:s){if(q.size()q.back()c){q.pop_back();continue;}q.push_back(c);}while(q.size()1q.front()q.back()){q.pop_front();q.pop_back();}coutn-q.size()\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t1;//cint;for(ll i1;it;i)solve();return0;}