Beautiful Binary String

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:

 1 2 3 4 5 6 7 8  n = input() B = list(input()) cnt = 0 for i in range(n): if B[i: i + 3] == ['0', '1', '0']: B[i + 2] = '1' cnt += 1 print(cnt) 

The code above works in-place 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):

 1 2 3  def beautifulBinaryString(b): bb = b.replace("010", "011") return sum(map(lambda x, y: x != y , zip(bb, b))) 

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

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  void replace_all(std::string& str, const char* what, const char* with) { auto pos = str.find(what); while (pos != std::string::npos) { str.replace(pos, strlen(what), with); pos = str.find(what, pos); } } int main() { int n; string s; cin >> n >> s; auto ss = s; replace_all(s, "010", "011"); cout << inner_product(begin(s), end(s), begin(ss), 0, plus<>{}, not_equal_to<>{}); } 

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:

 1 2 3 4  static void beautifulBinaryString(String B) { System.out.println((B.length() - B.replaceAll("010", "").length())/3); } 

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

 1 2  def beautifulBinaryString(b): return len(b.split("010")) - 1 

Actually, we can do even better not changing the string at all and working in-place.

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:

 1 2  input() # just ignore print(input().count("010")) 

We basically count how many times the pattern “010” appears in the input string, ignoring overlapping matches.

Haskell breakOnAll finds all non-overlapping instances of needle in haystack.

Alternatives

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

We've worked on this challenge in these gyms: modena  padua  Turin