Paint house: cheapest daily colors with no color twice in a row

A store sells blue, green and red shirts for the next n days, and each color's price changes by day. You buy exactly one shirt each day and may not buy the same color on two consecutive days. Return the color you buy on each day so that the total cost is as small as possible.

Interface

Unless you agree on a different interface with the interviewer, assume:

• lowest_cost(blue_costs: list[int], green_costs: list[int], red_costs: list[int]) -> list[str] — the color for each day: 'b', 'g' or 'r'. Neighbouring days differ; a color may repeat on days that are not consecutive.

Example

lowest_cost([7, 3, 8, 2], [2, 9, 4, 6], [5, 1, 9, 7])  ->  ['g', 'r', 'g', 'b']   # 2 + 1 + 4 + 2 = 9
lowest_cost([1, 2], [2, 100], [3, 100])               ->  ['g', 'b']             # 4: skips day 0's cheapest blue
lowest_cost([5], [3], [4])                            ->  ['g']

Constraints

• The three lists have the same length n, 1 <= n <= 10^5.
• 1 <= cost <= 10^4.
• The inputs have exactly one cheapest valid sequence.

Clarifying questions

• Return the sequence, the total, or both?
• If several sequences tie for the cheapest, which one should I return?
• Can a list be empty?
• Will there ever be more than three colors?

What a strong answer covers

• Why greedy fails: the cheapest color each day can repeat, and fixing one clash can cost more elsewhere (the second example).
• DP over days with state = the color bought that day: cost[i][c] = price[i][c] + min(cost[i-1][c']) for c' != c. O(n) time.
• Reconstructing the sequence: keep each choice's predecessor, or walk back from the cheapest final color choosing a consistent previous color. O(n) memory for the path; O(1) if only the total is needed.
• Edge cases: one day, two days, equal prices.
• A brute-force check over all 3^n sequences for small n.

Follow-ups

• k colors instead of three: get each day's step to O(k), not O(k^2), by keeping the best and second-best previous costs.
• You may not repeat a color within any three consecutive days.
• Return the total only, in O(1) memory.