Your team is developing a new feature called "Segmentify." This feature applies to a video with n (even) visual frames, where each frame is represented by a binary character in the array frames. In this format, a "0" represents a black pixel, and a "1" represents a white pixel.
Due to factors like lighting and camera angles, some frames may need horizontal or vertical flips (changing "0"s to "1"s and vice versa) to create consistent visuals. The objective is to divide the video into subsegments so that all frames in a subsegment are visually identical (i.e., the frames in a subsegment are either all "0"s or all "1"s). Additionally, each subsegment should have an even length.
The goal is to accomplish this segmentation with two criteria in mind:
1. Minimize the number of flips required to form valid segments, let this be denoted by B.
2. Among all configurations requiring B flips, minimize the total number of subsegments.
Given the binary string frames, determine the minimum number of even-length subsegments that can be created while utilising the least number of flips.
Note: A subsegment is a segment that can be derived from another segment by deleting some elements without changing the order of the remaining elements.
Example
Given frames = "1110011000", one set of optimal moves is as follows -
Flip the first 0 to 1 (1110011000) → 1111011000
Flip the first 0 to 1 (1111011000) → 1111111000
At last, again flip the first 0 to 1 (1111111000) → 1111111100
Hence, the length of all subsegments - (11111111 and 00) is even.
So, the minimum number of subsegments that frames can be divided into to make it "Segmentify-compliant" is 2 with minimum flips of 3.
Hence, the answer is 2.
Due to factors like lighting and camera angles, some frames may need horizontal or vertical flips (changing "0"s to "1"s and vice versa) to create consistent visuals. The objective is to divide the video into subsegments so that all frames in a subsegment are visually identical (i.e., the frames in a subsegment are either all "0"s or all "1"s). Additionally, each subsegment should have an even length.
The goal is to accomplish this segmentation with two criteria in mind:
1. Minimize the number of flips required to form valid segments, let this be denoted by B.
2. Among all configurations requiring B flips, minimize the total number of subsegments.
Given the binary string frames, determine the minimum number of even-length subsegments that can be created while utilising the least number of flips.
Note: A subsegment is a segment that can be derived from another segment by deleting some elements without changing the order of the remaining elements.
Example
Given frames = "1110011000", one set of optimal moves is as follows -
Flip the first 0 to 1 (1110011000) → 1111011000
Flip the first 0 to 1 (1111011000) → 1111111000
At last, again flip the first 0 to 1 (1111111000) → 1111111100
Hence, the length of all subsegments - (11111111 and 00) is even.
So, the minimum number of subsegments that frames can be divided into to make it "Segmentify-compliant" is 2 with minimum flips of 3.
Hence, the answer is 2.
Solution

Get one-to-one training from Google Facebook engineers
Top-notch Professionals
Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.
Customized Private Class
Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.