题解：P15629 [2019 KAIST RUN Spring] Rainbow Beads

· · 题解

题意解析

题目要求我们找到给定字符串中最长的不包含 VV，RV，VR，BV，VB，RR，BB 这 7 种子串的子串。

思路介绍

我们先来考虑不包含上述子串的子串的一些基本性质。容易看出，所有满足要求的长度极大的子串必定不会重叠，且由于单个字符满足条件，不存在一个满足条件的子串不是上面任何子串的子串。

我们换一个说法来解释这一点，那就是给定的字符串可以分割成若干个“色彩丰富”的长度极大的字符串，且长度最大的那一个必定能被分割出来。

于是，我们考虑使用双指针。记 l,r 表示当前区间的左右端点，当 r 处出现上述 7 种子串，那么视为分割成功一次，将当前的 l,r 视为一个分割结果。分割结束后，取 r-l+1 最大值即可。

代码分析

#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
    int ans=0;
    int l=0,r=0;
    cin>>s>>s;
    do{
        while(r<s.size()-1 && s[r]!=s[r+1] && s[r]!= 'V' && s[r+1]!='V') r++;
        ans=max(ans,r-l+1);
        l=r=r+1;
    }while(r<s.size()-1);
    cout<<ans;
}