Maximize vacation streak with PTO
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Given an array of characters containing 'w' (workday) and 'h' (holiday) and an integer n representing the number of PTO days you can convert from workdays, design an algorithm to find the maximum possible length of consecutive days off (holidays plus converted PTO days). Explain the time and space complexity and outline a sliding-window solution.
Quick Answer: This question evaluates proficiency in algorithmic problem-solving with arrays, specifically reasoning about consecutive subarray computations, linear-time scanning techniques, and the ability to analyze time and space complexity.
You are given a string days consisting only of 'h' (holiday) and 'w' (workday), and an integer n representing how many workdays you can convert to holidays (PTO). Return the maximum possible length of a contiguous block of days off after converting at most n 'w' characters to 'h'.
Constraints
- 0 <= len(days) <= 200000
- days[i] is either 'h' or 'w'
- 0 <= n <= len(days)
- Return 0 if days is empty
- Answer is in the range [0, len(days)]
Solution
def max_vacation_streak(days: str, n: int) -> int:
left = 0
w_count = 0
best = 0
for right, ch in enumerate(days):
if ch == 'w':
w_count += 1
while w_count > n:
if days[left] == 'w':
w_count -= 1
left += 1
curr_len = right - left + 1
if curr_len > best:
best = curr_len
return best
Explanation
Use a sliding window with two pointers (left and right). Expand right to include more days and track the number of 'w' in the window. If the number of 'w' exceeds n, increment left while decrementing the 'w' count as needed to restore validity (at most n 'w'). Update the best length at each step. This finds the longest subarray that can be made all holidays by converting at most n workdays.
Time complexity: O(n). Space complexity: O(1).
Hints
- Think in terms of the longest window containing at most n workdays.
- Maintain a sliding window with two pointers and a count of 'w' inside it.
- When the count of 'w' exceeds n, move the left pointer to shrink the window until it is valid again.