Segmentify: Minimum Subsegments
Updated
Problem statement
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 character of the string 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 (a flip changes one character of frames: a "0" becomes a "1" or a "1" becomes a "0") 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:
- Minimize the number of flips required to form valid segments, let this be denoted by
B. - Among all configurations requiring
Bflips, 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 contiguous part of frames. The subsegments must cover every frame exactly once.
Function
getminSubsegments(frames: String) → int Complete the function getminSubsegments in the editor.
getminSubsegments has the following parameter:
string frames: the frames of the video
Returns int: the minimum number of subsegments.
Examples
Example 1
frames = "1110011000"return = 2Indices are 0-based. Every subsegment has even length, so cuts can only fall at even positions, and each pair of frames (0, 1), (2, 3), (4, 5), (6, 7), (8, 9) ends up inside one subsegment and must become "00" or "11". The pairs are "11", "10", "01", "10" and "00": three of them differ, and each needs one flip, so at least B = 3 flips are needed. Flip index 3, then index 4, then index 7: "1110011000" becomes "1111011000", then "1111111000", then "1111111100", which splits into "11111111" and "00". With only 3 flips, the first pair "11" and the last pair "00" cannot change, so 1 subsegment is impossible. The answer is 2.
Example 2
frames = "110011"return = 3Indices are 0-based. The pairs of frames (0, 1), (2, 3), (4, 5) are "11", "00" and "11". They are all uniform, so B = 0 flips are needed, and with no flips the frames split into "11", "00" and "11". Fewer subsegments would need flips, and the number of flips is minimized first. The answer is 3.
Example 3
frames = "100110"return = 1Indices are 0-based. The pairs of frames (0, 1), (2, 3), (4, 5) are "10", "01" and "10". Each pair differs, so B = 3 flips are needed, one per pair. Flip index 1, then index 2, then index 5 (each time the first 0): "100110" becomes "110110", then "111110", then "111111", which is a single subsegment of length 6. The answer is 1.
Constraints
2 <= n <= 10^5, wherenis the length offrames, andnis evenframescontains only the characters'0'and'1'
More Amazon interview questions
- Get Smallest Base SegmentOA · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
- Minimum Grid InconvenienceOA · Seen Nov 2026
- 3SumPHONE SCREEN · Seen Nov 2026
- Circular Primes Below a LimitPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
- Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions
- Maximize Beautiful SubstringsFortinet · OAFortinet interview questions
- Wildcard MatchingTripjack · ONSITE INTERVIEWTripjack interview questions
- Match a Pattern With ? and *Adobe · PHONE SCREENAdobe interview questions
- Most Relevant Text SpanHebbia · PHONE SCREEN
- Split Array Largest SumAuxoAI · OA
- Longest Repeated Letter Block with Adjacent SwapsIntuit · OAIntuit interview questions
- Get Minimum IncrementIBM · OAIBM interview questions
- Binary CircuitAkuna Capital · OAAkuna Capital interview questions
- String Formation (Also for AI/ML Software Engineer Intern :)Snowflake · OASnowflake interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences