FastPrepSegmentify: Minimum Subsegments
Problems/Segmentify: Minimum Subsegments

Segmentify: Minimum Subsegments

Amazon logoAmazon● HardNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

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 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 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 = 2

Indices 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 = 3

Indices 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 = 1

Indices 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, where n is the length of frames, and n is even
  • frames contains 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
See Amazon hiring insights
Saved
class Solution {
    public int getminSubsegments(String frames) {
      // write your code here
    }

}
Checking account…