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.
Overview: 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)]
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.