Maximize pay by flipping k rest days
Company: Adobe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given integers BasePay and Bonus, a binary string schedule of length n where '1' means work and '0' means rest, and an integer k, you may change up to k zeros to ones. Pay rules: each workday earns BasePay; if day i and day i-1 are both workdays, you earn an additional Bonus for day i. Return the maximum total pay achievable after up to k flips. Describe your algorithm and analyze its time and space complexity.
Quick Answer: This question evaluates algorithm design and optimization skills in string processing and combinatorial decision-making, testing how to maximize weighted sequences of workdays under a limited number of flips.
Choose up to k rest days to work to maximize base pay plus adjacent-work bonuses.
Constraints
- schedule contains 0/1
Examples
Input: (10, 5, '1010', 1)
Expected Output: 40
Explanation: Flip one rest day to connect work streak.
Input: (10, 5, '000', 2)
Expected Output: 25
Explanation: Choose two adjacent workdays.
Input: (3, 10, '111', 1)
Expected Output: 29
Explanation: Already all work.
Input: (7, 2, '', 3)
Expected Output: 0
Explanation: Empty schedule.
Hints
- Dynamic programming over day, flips used, and whether the previous day is worked.