Distinct Zero-Run Lengths
Autumn Tournament (2013)
Submission name: zero.cpp
Problem summary
Given a binary string, consider its maximal contiguous runs of zeroes. Count how many distinct lengths occur among these runs.
Input
One nonempty string consisting only of 0 and 1.
Output
The number of distinct lengths of maximal zero runs.
Constraints
String length at most 10000.
Worked example
Original statement sample, with whitespace restored where PDF extraction merges adjacent numbers.
Input
1001000
Output
2
Solution analysis
- Maintain currentLength for the zero run currently being read. Each zero extends it. A one ends the run; record its positive length in a boolean seen array and reset currentLength.
- After processing the string, record currentLength once more if positive. This handles a run ending at the final character. Finally count the true flags, rather than counting how many runs were encountered.
- For 1001000, the maximal zero runs have lengths two and three, so the answer is two. For 1001001 there are two runs but both have length two, so the answer is one. For 0000 there is one maximal run of length four, not four different substrings.
Why it works
Each maximal zero run is recorded exactly when its following one is read, or once after the loop if it reaches the end. The boolean array merges equal lengths and includes every observed positive length, so its number of true entries is the desired count.
Watch out. Count maximal runs, not every all-zero substring. Do not count a run of length zero between adjacent ones. Remember to record a trailing zero run. A string of only ones has answer zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
string text;
cin>>text;
vector<bool>seen(text.size()+1,false);
int currentLength=0;
for(char symbol:text){
if(symbol=='0'){
++currentLength;
}
else{
if(currentLength>0){
seen[currentLength]=true;
}
currentLength=0;
}
}
// A final zero run has no following one to terminate it.
if(currentLength>0){
seen[currentLength]=true;
}
int answer=0;
for(bool present:seen){
if(present){
++answer;
}
}
cout<<answer<<'\n';
}