Beautiful Binary String

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

In-place readonly solutions

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.

1
2
3
4
5
6


import Data.Text (breakOnAll, pack)

main = do
    _ <- getLine
    xs <- getContents
    print . length $ breakOnAll (pack "010") (pack xs)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int main()
{
  char *s, *p;
  int n, rc=0;
  scanf("%d\n", &n);
  scanf("%ms", &s);
  while (p=strstr(s,"010"))
    ++rc, s=p+3;
  printf("%d\n", rc);
  return 0;
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


string s;
cin >> s;
auto count = 0;
for (auto i=2u; i<s.size(); ++i)
{
    if (s[i]=='0' && s[i-1]=='1' && s[i-2]=='0')
    {
        count++;
        i+=2;
    }
}
cout << count;

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 in-place vs copy.

Stream

This solution can handle a possible infinite input.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


int main() {
    std::cin.ignore(4, '\n'); // ignore first line
    char l = std::cin.get();
    char c = std::cin.get();
    int count = 0;
    while (std::cin) { // read until end of file
        char r = std::cin.get();
        if (l == '0' && c == '1' && r == '0') {
            r = '1';
            ++count;
        }
        l = c;
        c = r;
    }
    std::cout << count << std::endl;
}

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

1
2
3
4
5
6
7


keepOrFix (count, (l, c)) r = if (l, c, r) == ('0', '1', '0')
                              then (count + 1, (c, '1'))
                              else (count    , (c,  r ))
main = do
    _ <- getLine
    l:c:rs <- getContents
    print . fst $ foldl keepOrFix (0, (l, c)) rs

Alternatives

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

strings