See the original problem on HackerRank.
Solutions
The problem can be solved with a greedy algorithm: replace all 010
with
011
. Anytime a replace is performed, a counter is incremented:


The code above works inplace but it does modify the input string.
The following snippet, instead, does a copy of the string and exploits a few patterns (replace, sum, map, zip):


This one implements the same idea in C++ (much more verbose):


A slightly different solution consists in:
 removing all
010
from the string  subtracting the final length from the original length
 dividing the result by 3 (because we have removed 3 characters at a time)
That’s the implementation in Java:


It’s worth mentioning an alternative “just for fun” solution by Elia Giacobazzi and Roberto Melis:


Inplace readonly solutions
Actually, we can do even better not changing the string at all and working inplace.
Simple observation: anytime we find an overlapping match like “01010”, we can ideally turn the middle “0” into “1” and fix both “010” matches. Basically, if we search for “010” we should just ignore overlapping matches.
Python’s count
does what we mean:


We basically count how many times the pattern “010” appears in the input string, ignoring overlapping matches.
Haskell breakOnAll
finds all nonoverlapping instances of needle in haystack.


It can be done in C, using the function strstr
to search the pattern and
search the next occurrence starting from the end of the just found one. strstr
return a pointer (in this example p
) to the first character of the needle.
In the next loop, the pointer p
is incremenented by 3, i.e. the needle length.
Solution by Michele Liberi


A very similar idea in a more verbose C++ snippet:


If we find a match for “010” we increment a counter. Since we can ideally turn the last “0” to “1”, the next possible match is 2 steps away from the current position.
We discussed a bit about the tradeoff inplace vs copy.
Stream
This solution can handle a possible infinite input.


And can be translated to pure functional style in Haskell, using foldl
:


Alternatives
Another one that is left to the reader is the flexibility of the solution when the pattern to match changes.