AMAZON Coding Question – Solved

Amazon Prime Video 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 such subsegments that meet the criteria. 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: `frames = "1110011000"` One set of optimal moves is as follows: - Flip the first 0 to 1 → "1111011000" - Flip the next 0 to 1 → "1111111000" - Flip the final 0 to 1 → "1111111100" All resulting subsegments (11111111 and 00) are of even length. So, the minimum number of subsegments is 2 with a total of 3 flips. Hence, the answer is 2. Another example: `frames = "110011"` In this case, the string already consists of groups of "0"s and "1"s that have even lengths. Therefore, no flipping is necessary, and the string can be divided into 3 even-length subsegments without modification. Hence, the answer is 3. Function Description: Complete the function `getminSubsegments` in the editor below. `getminSubsegments` has the following parameter: - string `frames`: the frames of the video as a binary string. Returns: - int: the minimum number of subsegments. Constraints: - 2 ≤ n ≤ 10^5, where n is even. - It is guaranteed that the string `frames` only consists of '0's and '1's. Sample Input: `100110` Sample Output: 2 Explanation: Flip the first 0 to 1, resulting in "110110". All segments can then be grouped into even-length parts.