小红的环形字符串
时间限制：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。
- 使用双端队列
deque<char>模拟栈：- 遍历字符串s ss的每个字符c cc：
- 若队列非空且队尾字符等于c cc，则弹出队尾（消除一对）；
- 否则将c cc压入队尾。
- 遍历字符串s ss的每个字符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)。
总结
利用栈在线性消除相邻相同字符，再通过双端队列处理环形首尾可能存在的消除。核心在于理解环形结构使得首尾字符也可能相邻，因此需要在一次线性消除后继续检查首尾。该方法简洁高效，完美解决了环形字符串的消除问题。
代码内容
#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=998244353;voidsolve(){ll n;cin>>n;string s;cin>>s;deque<char>q;for(auto&c:s){if(q.size()&&q.back()==c){q.pop_back();continue;}q.push_back(c);}while(q.size()>1&&q.front()==q.back()){q.pop_front();q.pop_back();}cout<<n-q.size()<<"\n";}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t=1;//cin>>t;for(ll i=1;i<=t;i++)solve();return0;}
