Cheapest Daily Shirt Colors With No Color Repeated on Consecutive Days
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
A store has a sale on blue, green and red shirts for the next `n` days. On day `i`, a blue shirt costs `blue_costs[i]` dollars, a green shirt costs `green_costs[i]` dollars, and a red shirt costs `red_costs[i]` dollars. You want to buy exactly one shirt on each of the `n` days, but you cannot buy the same color on two consecutive days.
Return the color to buy on each day so that the total cost of the `n` shirts is minimized.
### Function Signature
```python
def lowest_cost(blue_costs: list[int], green_costs: list[int], red_costs: list[int]) -> list[str]:
```
Day `i` corresponds to index `i` of each list, starting from 0.
### Rules
- Return a list of length `n` whose element `i` is `'b'`, `'g'` or `'r'`: the color of the shirt bought on day `i`.
- Two adjacent elements of the returned list must differ.
- The total cost is the sum, over all days, of the price of the color chosen that day, and it must be the minimum over all valid color sequences.
- The input guarantees that exactly one valid color sequence achieves the minimum, so the answer is unique.
### Constraints
- `1 <= n <= 10^5`, and the three lists all have length `n`.
- Every price is an integer with `1 <= price <= 10^4`, so every total is at most `10^9` and fits in a 32-bit signed integer.
- Exactly one valid color sequence has the minimum total cost.
### Examples
**Example 1**
```text
Input: blue_costs = [1, 1, 1], green_costs = [3, 5, 7], red_costs = [4, 6, 4]
Output: ['b', 'g', 'b']
```
The total is 1 + 5 + 1 = 7. Buying blue every day would be cheapest, but two consecutive days cannot have the same color.
**Example 2**
```text
Input: blue_costs = [18, 12, 1, 9], green_costs = [13, 15, 7, 9], red_costs = [12, 16, 4, 8]
Output: ['r', 'g', 'b', 'r']
```
The total is 12 + 15 + 1 + 8 = 36.
**Example 3**
```text
Input: blue_costs = [100, 1, 76, 14], green_costs = [22, 20, 1, 2], red_costs = [99, 99, 5, 12]
Output: ['g', 'b', 'r', 'g']
```
The total is 22 + 1 + 5 + 2 = 30. Green on day 2 costs only 1, but taking it would force a color other than green on day 3, where green is the cheapest at 2; the unique optimum takes red on day 2 instead.
Overview: Pick a blue, green or red shirt for each of n days so that the total price is as low as possible while never buying the same color on two consecutive days, and return the chosen color sequence. It tests dynamic programming over a small state space and reconstruction of the optimal choices.
A store has a sale on blue, green and red shirts for the next `n` days. On day `i`, a blue shirt costs `blue_costs[i]` dollars, a green shirt costs `green_costs[i]` dollars, and a red shirt costs `red_costs[i]` dollars. Day `i` corresponds to index `i` of each list, starting from 0.
You want to buy exactly one shirt on each of the `n` days, but you cannot buy the same color on two consecutive days. Return the color to buy on each day so that the total cost of the `n` shirts is minimized.
Implement `lowest_cost(blue_costs, green_costs, red_costs)`:
- Return a list of length `n` whose element `i` is `'b'`, `'g'` or `'r'`: the color of the shirt bought on day `i`.
- Two adjacent elements of the returned list must differ.
- The total cost is the sum, over all days, of the price of the color chosen that day, and it must be the minimum over all valid color sequences.
- The input guarantees that exactly one valid color sequence achieves the minimum, so the answer is unique and no tie-breaking rule is needed.
### Constraints
- `1 <= n <= 10^5`, and the three lists all have length `n`.
- Every price is an integer with `1 <= price <= 10^4`, so every total is at most `10^9` and fits in a 32-bit signed integer (no value ever exceeds `2^31 - 1`).
- Exactly one valid color sequence has the minimum total cost.
### Example 1
```text
Input: blue_costs = [1, 1, 1], green_costs = [3, 5, 7], red_costs = [4, 6, 4]
Output: ['b', 'g', 'b']
```
The total is 1 + 5 + 1 = 7. Buying blue every day would be cheapest, but two consecutive days cannot have the same color.
### Example 2
```text
Input: blue_costs = [100, 1, 76, 14], green_costs = [22, 20, 1, 2], red_costs = [99, 99, 5, 12]
Output: ['g', 'b', 'r', 'g']
```
The total is 22 + 1 + 5 + 2 = 30. Green on day 2 costs only 1, but taking it would force a color other than green on day 3, where green is the cheapest at 2; the unique optimum takes red on day 2 instead.
Constraints
- 1 <= n <= 10^5, and blue_costs, green_costs and red_costs all have length n.
- Every price is an integer with 1 <= price <= 10^4.
- Every total is at most 10^9, so it fits in a 32-bit signed integer (never exceeds 2^31 - 1).
- Exactly one valid color sequence (no two consecutive days with the same color) has the minimum total cost.
Examples
Input: ([1, 1, 1], [3, 5, 7], [4, 6, 4])
Expected Output: ['b', 'g', 'b']
Explanation: Source Example 1: blue is strictly cheapest every day, so the optimum alternates blue with the next-best color; total 1 + 5 + 1 = 7.
Input: ([18, 12, 1, 9], [13, 15, 7, 9], [12, 16, 4, 8])
Expected Output: ['r', 'g', 'b', 'r']
Explanation: Source Example 2: total 12 + 15 + 1 + 8 = 36; on the last day blue and green both end at 37, red at 36.
Hints
- Example 2 shows that taking the cheapest allowed color day by day from the start can cost more overall: a cheap choice on one day can block an even cheaper color on the next day.
- The no-repeat rule only links each day to the day immediately before it.
- Because the minimum-cost sequence is guaranteed to be unique, you never need a tie-breaking rule, and every total stays at most 10^9.