首页 > 试题广场 >

橡皮泥斑马

[编程题]橡皮泥斑马
  • 热度指数：2624 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小易很喜欢斑马，因为它们身上黑白相间的花纹。
一天小易得到了一串橡皮泥，这串橡皮泥只有黑色和白色，小易想把这串橡皮泥重新拼凑一下，让这个橡皮泥串中最长的连续的黑白相间的子串最长，但是小易有强迫症，所以他可以对橡皮泥串进行以下的操作0次或多次：
把橡皮泥串从某个地方切割开，将两个得到的两个串同时翻转，再拼接在一起。
这个橡皮泥串可能太长了，所以小易没有办法计算最终可以得到的最长的连续的黑白相间的子串的长度，希望你能帮他计算出这个长度。

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


输出描述:
一个整数，表示改变之后最长的连续的黑白相间的子串的长度。
示例1

输入

bwbwb

输出

5
示例2

输入

wwb

输出

3
算法知识视频讲解
添加回答
月亮上的熊猫头像 月亮上的熊猫
该变换规则不影响相对位置，计数时记得把头尾可拼接的情况考虑进去。 
s = list(input())
n = len(s)

res = 0
pre = 0
post = n-1
if s[0] != s[-1]:
    while(s[pre] != s[pre+1]):
        pre += 1
    while(s[post] != s[post-1]):
        post -= 1
    res = n - post + pre + 1
tmp = 1
for i in range(n-1):
    if s[i]!=s[i+1]:
        tmp += 1
    else:
        res = max(res,tmp)
        tmp = 1
res = max(res,tmp)
print(res)


编辑于 2019-08-24 16:35:44 回复(0)
Python
ElonB头像 ElonB 
"""
将串首尾相连成环(简化为将S加上一个首字符)，计算最长子串
能通过本题的所有测试用例
"""

if __name__ == "__main__":
    s = input().strip()
    s = s + s[0]
    ans, tmp = 0, 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            ans = max(ans, tmp)
            tmp = 1
        else:
            tmp += 1
    ans = max(ans, tmp)
    print(ans)

编辑于 2019-08-24 16:27:40 回复(5)
pein531头像 pein531
两个子橡皮泥串同时翻转就相当于把后面的子串拼到前面去。因此可以将原始橡皮泥串重复两遍，然后计算最长黑白相间的子串长度。但是这个长度不能超过原始橡皮泥串的长度。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 因为把字符串切割后同时翻转在拼接相当于将后面的子串放到前面去，因此将原字符串扩大两倍后寻找最长相间子串即可
        String str = br.readLine().trim();
        str += str;
        int maxLen = 0;
        for(int i = 0; i < str.length(); i++){
            int j = i + 1;
            while(j < str.length() && str.charAt(j) != str.charAt(j - 1))
                j ++;
            // 不能超过原字符串长度
            if(j - i <= str.length() / 2)
                maxLen = Math.max(maxLen, j - i);
            else
                break;
        }
        System.out.println(maxLen);
    }
}


发表于 2021-01-30 18:42:49 回复(0)
C/C++
卷积神经网络哦头像 卷积神经网络哦
看大家都是环  恍然大悟 。。鄙人思路和代码相当复杂，但也能过。 
#include<bits/stdc++.h>
using namespace std;
string s;

string op(string s, int pos) {
	//在pos位置对字符串s进行题目所示操作
	if(pos >= s.length()) return s;
    string ls = s.substr(0, pos);
    string rs = s.substr(pos);
	reverse(ls.begin(), ls.end());
	reverse(rs.begin(), rs.end());
    return ls + rs;
}

vector<int> cal_length(string s) { //找到最长间隔串并返回长度和左右坐标
	int len = 1, res = 1, cur_l = 0, cur_r = -1;
	char last = s[0];
	for(int i = 1; i < s.length(); i++) {
		if(s[i] != last) len++;
		else {cur_l = i; len = 1; }
		if(len > res) {res = len; cur_r = i; }
		last = s[i];
	}
	vector<int> ve;
	if(res == 1) res = 0;
	ve.push_back(res);
	ve.push_back(cur_l);
	ve.push_back(cur_r);
	return ve;
}

int main() {
	cin>>s;
	int s_len = s.length();
    vector<int> v_cur = cal_length(s);
	int best = v_cur[0];
	while(v_cur[0] != s_len && s[0] != s[s_len - 1]) { //满足换了之后可以增加长度
		string cur_s1 = op(s, v_cur[2]+1); // 在当前最长的右边节点换
		string cur_s2 = op(s, v_cur[1]); // 当前最长的左边节点换
		vector<int> v1 = cal_length(cur_s1); 
		vector<int> v2 = cal_length(cur_s2);
		if(v1[0] > 0 && v1[0] >= v2[0] && v1[0] > v_cur[0]) {
			best = v1[0]; s = cur_s1; v_cur = v1;
		} else if(v2[0] > 0 && v1[0] < v2[0] && v2[0] > v_cur[0]) {
			best = v2[0]; s = cur_s2; v_cur = v2;
		} else {
			break;
		}
	} 
	cout<<best<<endl;
}
/*
bwbwb
wwb
*/

发表于 2020-01-18 16:14:21 回复(2)
Unlimited_Blade_Works头像 Unlimited_Blade_Works 
//因为可以成环，因此最长的结果为两种情况
//1.正常扫描下来最长的结果
//2.以序列头开始的连续部分和以序列末尾结束的连续部分之和（序列头和序列尾不同）
//取这两种情况中的最大值
#include <stdio.h>
#include <string.h>

const int N = 1e5;
char str[N+5];

int max(int a,int b){
    return a>b?a:b;
}

int main(){
    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;
}
编辑于 2019-08-13 17:12:07 回复(0)
老面馒头五毛钱一个嘿嘿头像 老面馒头五毛钱一个嘿嘿 
s = raw_input()
s = s + s
res = 0
for i in range(len(s)):   
    j = 1
    while i < len(s)-1 and s[i] != s[i+1]:
        j += 1
        i += 1
    if j > res:
        res = j
if res > len(s)/2:
    res = len(s)/2
print res

发表于 2019-05-29 19:46:50 回复(0)
凉兮201801121950535头像 凉兮201801121950535
字符串翻转，可以将其理解为环形结构，相对位置不变
发表于 2019-05-02 14:26:35 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    int Max=0,t=1;
    s += s[0];
    for(int i=1;i<s.length();i++){
        if(s[i]!=s[i-1])
            t++;
        else{
            if(t>Max)
                Max = t;
            t = 1;
        }
    }
    if(t>Max)
        Max = t;
    cout<<Max<<endl;
    return 0;
}

发表于 2019-08-28 00:47:29 回复(3)
Dave_lzw头像 Dave_lzw 
/*切割并同时旋转拼接 相当于 把切割后 后面的子串 放到 前面 
如wbwwb，切割wbw，wb 后放前 -> wbwbw 与翻转（wbw,bw）后拼接结果一致
故将原字符串扩大2倍，找最长相间子串
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s ; 
    cin >> s ; 
    s += s ;
    int len = s.size() ;
    int res = 0 ; 
    for( int i = 0 ; i < len ; i++ ){
        int j = i + 1 ;
        while( j < len && s[j] != s[j-1] ){
            j ++ ;
        }
        res = max( res , j - i ) ; 
        i = j - 1 ;
    }
    cout << min( res , len / 2 ) << endl ;
    return 0 ; 
}

发表于 2020-02-11 16:20:38 回复(0)
tridu33头像 tridu33 
// 取模转圈
#include<bits/stdc++.h>
using namespace std;

int main(){
    string str;
    getline(cin, str);
    str += str[0];
    int len = 0,curlen = 1;
    char pre = str[0];
    int n =str.size();
    for(int i =1; i<n * 2; i++){
        if(str[(i-1)%n] == str[i%n]){
            len = max(len,curlen);
            curlen = 1;
        }else{
            curlen ++;
        }
    }
    len = max(len,curlen);
    cout << len << endl;
    return 0;
}

发表于 2021-09-15 19:43:29 回复(0)
或非门头像 或非门
同时翻转是怎么一个翻转法？有哪个可以举一下例子？
发表于 2020-08-19 12:00:19 回复(0)
223s头像 223s
可以切割开，将两个得到的两个串同时翻转，再拼接在一起，可以看做一个首位相接的串，将串后面在拼接本身就行。然后就是查找最长bw子串问题了. 
import java.util.*;
public class Main{
    
    
    public static void main(String[] args){
        
       Scanner s  = new Scanner(System.in); 
       String str = s.nextLine();
       
       StringBuilder sb = new StringBuilder(str);
       sb.append(str);
        
       int len = 1;
       int maxLen = 1;
       for(int i =1;i<sb.length();i++){
           if(sb.charAt(i-1) != sb.charAt(i)){
               len+=1;
           }else{
               len = 1;
           }
           maxLen = maxLen>=len?maxLen:len;
       }
        
       System.out.println(maxLen);
        
    }
}
发表于 2020-08-13 13:29:01 回复(0)
干了这碗白开水头像 干了这碗白开水 
#include <iostream>
#include <string>
using namespace std;

int main(){
    string s;
    cin >> s;
    //如果字符串长度小于2
    if (s.size() <= 1) 
        cout << s.size() << endl;
    //正常情况
    else{
        int res = 1;
        //遍历每一个字符
        for (int i=0;i<s.size();++i){
            int cur = 0;
            //从当前字符开始，计算他的子串长度
            for (int j=0;j<s.size();++j){
                //把首尾相连
                if (s[(i+j)%s.size()] != s[(i+j+1)%s.size()])
                    ++cur;
                else
                    break;
            }
            //之所以➕1，因为虽然最后一个满足条件的字符和下一个字符一样了，但是它和上一个还是不一样的
            //所以这个字符的长度得算进去
            res = res<cur+1?cur+1:res;
        }
        cout << res << endl;
    }
    return 0;
}

发表于 2020-07-15 15:51:55 回复(0)
Python
杭执头像 杭执
测试用例不太严谨，我用的错误的方法结果还通过了，我看题解才知道我错了 
s = input()
t = s[0]
l_max = 0
l = 1
for i in range(1,len(s)):
    c = s[i]
    if c == t:
        if l_max < l:
            l_max = l
            l_max_0 = i - l + 1
        l = 1
    else:
        l += 1
    t = s[i]
if l_max == 0:
    l_max = l
    l_max_0 = 0
if l_max < l:
    l_max = l
    l_max_0 = i - l + 1
if s[0] != s[-1] and (l_max_0 == 0&nbs***bsp;l_max_0 == len(s) -l):
    l_max += 1
print(l_max)

发表于 2020-07-02 22:57:40 回复(0)
Java
时光无声201908231908920头像 时光无声201908231908920 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();

        str += str;

        int res = 0;
        int temp = 1;
        for (int i = 0; i < str.length() - 1; i++) {
            int j = i + 1;
            if (str.charAt(i) != str.charAt(j)){
                temp++;
                res = Math.max(res, temp);
            } else {
                temp = 1;
            }
        }

        if (res == str.length()){
            System.out.println(res / 2);
        } else {
            System.out.println(res);
        }

    }
}

发表于 2020-03-24 17:05:41 回复(0)
jahentao头像 jahentao 
import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        input += input;
        char[] s = input.toCharArray();
        int cur = 1, max = 0;
        for (int i = 0; i < s.length - 1; i++) {
            if (s[i] != s[i+1]) {
                cur += 1;
            } else {
                if (cur > max) {
                    max = cur;
                }
                cur = 1;
            }
        }
        System.out.println(max);
    }
}
任意位置分开，旋转，可理解为环形结构。上面的代码本来以为有通不过的，没想到一次通过了所有测试用例，只能说测试用例不完备哈哈。
发表于 2019-07-31 20:44:45 回复(0)
Robust-neu头像 Robust-neu 
//根据反转前后相对位置不变，相当于在一个环上找最长子串
#include <iostream>
#include <string>
using namespace std;
int main()
{ 
    string s;
    cin >> s;
    int g_l = 0, l_l = 1;
    s += s[0];//在字符串末尾加上第一个字符构成环
    for (int i = 0; i < s.size()-1; i++) {
        if (s[i] != s[i + 1]) {
            l_l++;
        }
        else{
            if (l_l > g_l) {
                g_l = l_l;
            }
            l_l = 1;
        }
    }
    if (l_l > g_l) {
        g_l = l_l;
    }
    cout << g_l;
    return 0;
}

发表于 2019-07-30 10:18:47 回复(0)
qing鹏头像 qing鹏 
 同样的算法思路，java跑过不了，c++能过
                                                                                    



                                        

                                            
                                                                                                                                                            发表于  2019-07-15 10:46:02
                                                    
                                                                                            
                                                回复(0)
                                                                                                                                            

                                        

                                


                                                            
                        

                        
                                        

                            

        


                    

                                    

                        

                            

                            

                                提交观点
                            

                        

                    

                            

            

    

          

            
问题信息

            

              

                                      C++工程师
                                      golang工程师
                                      iOS工程师
                                      安卓工程师
                                      字符串
                                      运维工程师
                                      前端工程师
                                      算法工程师
                                      测试工程师
                                      PHP工程师
                                      模拟
                                      网易
                                      2019
                                      拼多多集团-PDD
                                      Java工程师
                                

                                  

                
                                                      

                          上传者：小小
                      

                                              

                                        难度：

                                

                                        18条回答
                      
                      10868浏览
                                

            

          


                        

  

    

      
      
      
    

    
热门推荐

  

  

    

      
    

  



            

                

            

          
                          

                

                  
通过挑战的用户

                                          查看代码
                                    

                

                  
                

              

            
                          

                
相关试题

                

                  
                

              

            
                            

                        橡皮泥斑马
                

                





                
        

                                                                

        

    
    
    

    


            
    
    

        

            

                
            

            
扫一扫，把题目装进口袋

        

        

            
求职之前，先上牛客

            

                
                    

                        

                        

                            
                            
扫描二维码，进入QQ群

                        

                    

                
                
                    

                        

                        

                            
                            
扫描二维码，关注牛客公众号