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 ```python 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** ```text 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** ```text 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** ```text Input: blue_costs = [5], green_costs = [3], red_costs = [4] Output: ['g'] ``` With a single day, the cheapest shirt is the green one.