Bakery Relabeling Stretch

Longest subarray made constant within a per-element change-cost budget

MediumSliding WindowWeighted CostsFrequency Tracking

A bakery has a row of trays waiting for packaging. Tray i currently carries flavor label flavors[i]. Replacing that tray's label costs costs[i], regardless of which new flavor label is chosen.

The bakery wants to choose a nonempty contiguous stretch of trays and make every label in that stretch equal to one target flavor. Target flavors are the integers from 0 through 9. Trays already carrying the target flavor require no replacement and cost nothing. Every other tray in the chosen stretch must be relabeled.

The total replacement cost must be at most budget.

Return [start, end, target], where start and end are the inclusive, zero-based endpoints of the selected stretch. Choose the result using these priorities:

  1. Maximize the number of trays in the stretch.
  2. Among equally long stretches, choose the smallest start.
  3. For that stretch, choose the smallest target flavor whose replacement cost is within the budget.

The target flavor does not have to occur in the selected stretch before relabeling. If the row is empty, return [].

Examples

Example 1

Input: flavors = [2,1,2,3], costs = [5,2,4,6], budget = 2
Output: [0,2,2]

The first three trays can all receive flavor 2 by replacing only the middle tray's label. Extending through the final tray would exceed the budget for every target flavor.

Example 2

Input: flavors = [4,1,4], costs = [2,1,2], budget = 4
Output: [0,2,1]

The entire row can be standardized within the budget. Flavor 1 is the smallest feasible target, even though choosing flavor 4 would have a lower replacement cost.

Example 3

Input: flavors = [3,3,1,1], costs = [7,2,5,4], budget = 0
Output: [0,1,3]

With no relabeling budget, only stretches already carrying one flavor are eligible. Two stretches have the maximum length, so the earlier one is selected.

Constraints

  • 0 <= len(flavors) <= 100000
  • len(costs) == len(flavors)
  • 0 <= flavors[i] <= 9
  • 1 <= costs[i] <= 1000000
  • 0 <= budget <= 100000000000

The reference solutions run in O(n) time because there are exactly ten possible flavors, and use O(1) auxiliary space. Costs are charged per tray, not per unit of label difference.

Hints

Show hint 1

For a fixed stretch and target flavor, subtract the total cost attached to trays already carrying that flavor from the stretch's total cost.

Show hint 2

Track the total cost and ten per-flavor cost totals in a sliding window. Removing trays cannot make a feasible stretch infeasible.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you support arbitrary integer flavor labels without scanning every distinct flavor whenever the window changes?
  • How would the solution change if only a supplied subset of target flavors were permitted?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem