**PROBLEM LINKS:**

practice

contest

**Difficulty:**

Easy

**Pre-requirements:**

Greedy Techniques

**Problem:**

Given a binary string of **0**s and **1**s. Find the minimum number of flips required to change the string such that it does’nt contain the substring **101**.

**Explanation:**

Iterate from left to right and change every substring **101** to **100**.

Count number of such changes.

complexity: **O(N)** for each Test case.

**Authors Solution:**

can be found here

why did you change substring 101 to 100 not 111. please help

finding out total number of substring with 101 and changing them to 100

the reason we are changing them to 100 insted of 111 or 110 is because here we

are looking for minimum number of flips required to make that row into lazzle row

if we bring 1 in the string then that may not be efficient as there can be one more substring 01

in the string

ex: s = 101010101

Output = 2 i.e.,

flip - 1: s = 100010101

flip - 2: s = 100010001

1 Like