LZRW - Editorial

PROBLEM LINKS:

practice

contest

Difficulty:

Easy

Pre-requirements:

Greedy Techniques

Problem:

Given a binary string of 0s and 1s. 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