列表

详情


WY74. 橡皮泥斑马

描述

小易很喜欢斑马,因为它们身上黑白相间的花纹。
一天小易得到了一串橡皮泥,这串橡皮泥只有黑色和白色,小易想把这串橡皮泥重新拼凑一下,让这个橡皮泥串中最长的连续的黑白相间的子串最长,但是小易有强迫症,所以他可以对橡皮泥串进行以下的操作0次或多次:
把橡皮泥串从某个地方切割开,将两个得到的两个串同时翻转,再拼接在一起。
这个橡皮泥串可能太长了,所以小易没有办法计算最终可以得到的最长的连续的黑白相间的子串的长度,希望你能帮他计算出这个长度。

输入描述

一个字符串s,只包含字母'b'和字母'w',分别表示黑色和白色的橡皮泥块。
满足1 <= |s| <= 105,|s|代表字符串的长度。

输出描述

一个整数,表示改变之后最长的连续的黑白相间的子串的长度。

示例1

输入:

bwbwb

输出:

5

示例2

输入:

wwb

输出:

3

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2021-09-15

#include<stdio.h>
#include<string.h>

int main()
{
    char c[100001];
    scanf("%s",&c[0]);
    int len = strlen(c);
    c[len] = c[0];
    int max=0;
    for(int i=0;i<(len+2);i++)
    {
        int temp = 0;
        while(c[i] != c[i+1] && i<len)
        {
            i++;
            temp++;
        }
        if(temp>max)
            max = temp;
    }
    printf("%d",(max+1));
    return 0;
}

C++14 解法, 执行用时: 2ms, 内存消耗: 420KB, 提交时间: 2020-08-30

#include <stdio.h>
//#include <string>
#include <string.h>
//using namespace std;
const int N=1e5;
char str[N+5];
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    //string str;
    scanf("%s",&str);
    int len= strlen(str);
    if(len==1) puts("0");
    else if(len==2)
    {
        if(str[0]==str[1])
        {
            puts("0");
        }else
        {
            puts("2");
        }
    }else
    {
        int headLen=1,tailLen=1;
        int start=0,end=len-1;
        
        for(;start<end;start++)
        {
            if(str[start]==str[start+1]) break;
            headLen++;
        }
        if(start==end) printf("%d\n",headLen);
        else
        {
            for(;end>start;end--)
            {
                if(str[end]==str[end-1]) break;
                tailLen++;
            }
            int res=max(headLen,tailLen);
            int tmpLen=1;
            for(start++,end--;start<end;start++)
            {
                if(str[start]==str[start+1])
                {
                    res=max(res, tmpLen);
                    tmpLen=1;
                }else tmpLen++;
            }
            if(str[0]!=str[len-1]) res=max(res, headLen+tailLen);
            printf("%d\n",res);
        }
    }
    
        return 0;
}

上一题