Katkat
Back

Maximize Earnings by Converting Days Off

CitadelSoftware Engineer · HR Screen
MediumSoftware EngineerHR ScreenCoding & Algorithms

Last updated

Tests dynamic programming and state tracking to maximize daily earnings and consecutive work streak bonuses under a budget of schedule changes.

Problem Statement

You are given an employee's work schedule for the next n days, represented by a string schedule consisting of 'W' (workday) and 'O' (day off).

For each day i worked, the employee earns pay[i]. If the employee takes the day off, they earn 0 for that day. Additionally, the company rewards consistency: for every pair of consecutive days (i, i + 1) where both are workdays, the employee receives an extra fixed amount bonus.

You are allowed to convert at most k days off ('O') into workdays ('W'). Existing workdays cannot be converted to days off.

Write a function max_earnings(schedule: str, pay: list[int], bonus: int, k: int) -> int that returns the maximum total earnings achievable.

Function Signature

def max_earnings(schedule: str, pay: list[int], bonus: int, k: int) -> int:
    pass

Input & Output Format

  • Input:
    • schedule: A string of length n containing only 'W' and 'O'.
    • pay: A list of n non-negative integers representing daily pay.
    • bonus: A non-negative integer representing the bonus awarded for each adjacent pair of workdays.
    • k: An integer representing the maximum number of conversions permitted.
  • Output:
    • An integer representing the maximum total earnings.

Constraints

  • 1 <= n <= 1000
  • 0 <= k <= n
  • schedule has length n and contains only characters 'W' and 'O'
  • len(pay) == n
  • 0 <= pay[i] <= 10^5
  • 0 <= bonus <= 10^5

Examples

Example 1

Input: schedule = "W O O W", pay = [10, 5, 5, 10], bonus = 3, k = 1
Output: 28
Explanation:
Converting day 1 (0-indexed) gives "W W O W".
Daily pay: 10 + 5 + 10 = 25.
Adjacent workday pairs: (0, 1), earning 1 * 3 = 3 in bonuses.
Total earnings = 25 + 3 = 28.
Converting day 2 gives "W O W W", also yielding 28.
Converting none gives 20.

Example 2

Input: schedule = "O O O", pay = [20, 10, 20], bonus = 5, k = 2
Output: 40
Explanation:
Converting days 0 and 2 gives pay 20 + 20 = 40 (0 adjacent pairs).
Converting days 0 and 1 gives pay 20 + 10 = 30 plus 1 adjacent bonus = 35.
The optimal strategy is to convert days 0 and 2 for a total of 40.

Hints

Hint 1

Notice that the earnings on day i depend only on whether day i is worked and whether day i - 1 was worked.

Hint 2

Formulate a dynamic programming state dp(i, rem_k, prev_worked) representing the maximum earnings from day i onwards given the remaining budget of conversions and the status of day i - 1.

Hint 3

Because the transition for day i depends only on day i - 1, you can iteratively compute the DP table and optimize space to O(k).

Follow-up questions

  • How would you approach this problem if the consecutive bonus was non-linear (e.g., L^2 for a streak of length L)?
  • How can you optimize the space complexity of your solution from O(n * k) to O(k)?
  • If pay[i] was identical for every day, could you design an O(n log n) or O(n) greedy solution instead of dynamic programming?