P76031 消去异色两端 — 题解

专题： 双指针
适用题目： 新生 OJ 本地题包中的 P76031，不要直接用于外站同名题。

解题思路

只要左右指针所在字符不同，就同时向内部收缩；遇到相同字符或区间为空时结束。

复杂度

每组时间 $O(n)$，额外空间 $O(n)$。

易错点

不能跳过中间字符，也不能只删除一侧。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int t;scanf("%d",&t);static char s[100005];
    while(t--){int n;scanf("%d%100004s",&n,s);
        int l=0,r=n-1;
        while(l<r && s[l]!=s[r]){l++;r--;}
        printf("%d\n",r-l+1);
    }
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        string s;
        cin>>n>>s;
        int l=0,r=n-1;
        while(l<r&&s[l]!=s[r]){
            l++;
            r--;
        }
        cout<<max(0,r-l+1)<<nl;
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。