Cheapest Shirt Color Sequence With No Color Repeated on Consecutive Days

A store runs a sale on blue, green and red shirts for the next n days. On day i, a blue shirt costs blue_costs[i], a green shirt costs green_costs[i], and a red shirt costs red_costs[i].

You buy exactly one shirt on each of the n days, but you may not buy the same color on two consecutive days. Return the color you buy on each day so that the total cost of the n shirts is as small as possible.

Function Signature

def lowest_cost(blue_costs: list[int], green_costs: list[int], red_costs: list[int]) -> list[str]:

Rules

• Return a list of length n whose i-th element is the color bought on day i: 'b' for blue, 'g' for green, or 'r' for red.
• For every i from 1 to n - 1, the colors bought on day i - 1 and day i must differ. A color may repeat on days that are not consecutive.
• The inputs are guaranteed to have exactly one valid color sequence with the minimum total cost, so the expected output is unique.

Constraints

• The three lists have the same length n.
• 1 <= n <= 10^5 (the original only says the lists have length n; this bound is assumed for this practice version)
• Every cost is a positive integer; assume 1 <= cost <= 10^4, so every total fits in a 32-bit signed integer.

Examples

Example 1

Input: blue_costs = [7, 3, 8, 2], green_costs = [2, 9, 4, 6], red_costs = [5, 1, 9, 7]
Output: ['g', 'r', 'g', 'b']

The total is 2 + 1 + 4 + 2 = 9, and every other valid sequence costs more than 9.

Example 2

Input: blue_costs = [1, 2], green_costs = [2, 100], red_costs = [3, 100]
Output: ['g', 'b']

The total is 2 + 2 = 4. The other valid sequences cost 101 (blue, green), 101 (blue, red), 102 (green, red), 5 (red, blue) and 103 (red, green).

Example 3

Input: blue_costs = [5], green_costs = [3], red_costs = [4]
Output: ['g']

With a single day, the cheapest shirt is the green one.