题目描述
有一个长度为 n 的 01 串,其中有一些位置标记为 ?,这些位置上可以任意填充 0 或者 1,请问如何填充这些位置使得这个 01 串中出现互不重叠的 00 和 11 子串最多,输出子串个数。
样例
1110?0
2
算法1
(暴力枚举) $O(n)$
C++ 代码
#include<iostream>
using namespace std;
int main(){
string s;
int ans=0;
cin>>s;
if(s.length()==1)
{
cout<<ans;
return 0;
}
for(int i=0;i<s.length();i++)
{
if(s[i]==s[i+1]||s[i]=='?'||s[i+1]=='?')
{
ans++;
i++;
}
}
cout<<ans;
}