YetnotherrokenKeoard

wuyin331 · 2023-12-10 15:09:17 · 题解

题意

给你一个字符串 s。

如果出现字符 B，则删除最后出现的大写字母，若没有大写字母，则跳过。

如果出现字符 b，则删除最后出现的小写字母，若没有小写字母，则跳过。

题解

考虑从后面开始遍历字符串 s。因为从前面开始遍历字符串的话，要倒回去操作数组，较为麻烦，如果从后面开始遍历字符串的话，只要维护 B 与 b 的个数就行。同时，我们并不需要真正的删除字符串，只需要用一个数组来表示这个位置是否被删除即可。

代码

#include<iostream>
#include<cstdio>
#include<climits>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<unordered_map>
#include<unordered_set> 
#include<cmath>
#include<numeric>
#define int long long 
using namespace std;
int n,m,k,t;
int nums[1000005];
bool vis[1000005];
int gcd(int a,int b){
    if(b) while((a%=b)&&(b%=a));
    return a+b;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        for(int i=0;i<s.size();i++) vis[i]=0;
        int big=0,sma=0;
        for(int i=s.size()-1;i>=0;i--){
            if(s[i]=='B'){big++,vis[i]=1;continue;}
            if(s[i]=='b'){sma++,vis[i]=1;continue;}
            if(big&&s[i]>='A'&&s[i]<='Z'){
                big--;
                vis[i]=1;
                continue;
            }
            if(sma&&s[i]>='a'&&s[i]<='z'){
                sma--;
                vis[i]=1;
                continue;
            }
        }
        for(int i=0;i<s.size();i++){
            if(!vis[i]) cout<<s[i];
        }
        cout<<'\n';
    }
    return 0; 
}