Cheapest Shirt Color Sequence With No Color Repeated on Consecutive Days
Company: Elevenlabs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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.
Overview: Buy one blue, green or red shirt on each of n days without buying the same color on consecutive days, and return the color sequence with the lowest total cost. The task asks for the actual sequence rather than only the cost, testing optimization over sequences and reconstruction of the unique optimal choice.
Read the full Elevenlabs Software Engineer interview experience this question came from
A store runs a sale on blue, green and red shirts for the next `n` days. On day `i` (days are numbered from `0`), 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.
Implement `lowest_cost(blue_costs, green_costs, red_costs)`.
### Output
- 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 is at most `10^9` and fits in a 32-bit signed integer (no total exceeds `2^31 - 1`).
### 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).
Constraints
- The three lists blue_costs, green_costs and red_costs 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 (at most 10^9, never above 2^31 - 1).
- The inputs are guaranteed to have exactly one valid color sequence with the minimum total cost, so the expected output is unique.
Examples
Input: ([7, 3, 8, 2], [2, 9, 4, 6], [5, 1, 9, 7])
Expected Output: ['g', 'r', 'g', 'b']
Explanation: Sealed Example 1: each day's cheapest color (green, red, green, blue) already alternates; total 2 + 1 + 4 + 2 = 9.
Input: ([1, 2], [2, 100], [3, 100])
Expected Output: ['g', 'b']
Explanation: Sealed Example 2, n = 2: day 0's cheapest color (blue) is given up so day 1 can take blue; total 2 + 2 = 4.
Hints
- Taking the cheapest color on every day on its own can buy the same color on two consecutive days, and fixing one clash can make a neighbouring day more expensive.
- When you decide a day's color, ask what you need to remember about the days already planned for that choice to be both legal and as cheap as possible.
- The answer is the list of colors, not only the minimum total, so keep enough information to recover which choice was made on each day.