Maximize the longest vacation using PTO
Updated
•6 min readYou are given a calendar year represented as a character array containing only:
H= holidayW= workday
You are also given an integer pto, representing how many workdays you may convert into vacation days by using Personal Time Off.
Your goal is to maximize the length of the longest consecutive vacation streak, where a vacation day is either:
an existing holiday (
H), ora workday (
W) that you choose to cover with PTO
Return the maximum possible length of such a consecutive streak.
Example:
calendar = [W, H, H, W, W, H, W]pto = 2Output:
5
Explanation: By using PTO on two appropriate workdays, you can create a longest contiguous vacation block of length 5.
Solution
public class Solution {
// ──────────────────────────────────────────────────────────────────────────
// PROBLEM — Longest Vacation (Sliding Window)
// Time: O(n) | Space: O(1)
// ──────────────────────────────────────────────────────────────────────────
public static int longestVacation(char[] calendar, int pto) {
if (calendar == null || calendar.length == 0) return 0;
int left = 0, workdaysUsed = 0, maxStreak = 0;
for (int right = 0; right < calendar.length; right++) {
if (calendar[right] == 'W') workdaysUsed++;
while (workdaysUsed > pto) {
if (calendar[left] == 'W') workdaysUsed--;
left++;
}
maxStreak = Math.max(maxStreak, right - left + 1);
}
return maxStreak;
}
// ──────────────────────────────────────────────────────────────────────────
// FOLLOW-UP A: Return the actual START and END indices of the best window
// Time: O(n) | Space: O(1)
// ──────────────────────────────────────────────────────────────────────────
public static int[] longestVacationRange(char[] calendar, int pto) {
if (calendar == null || calendar.length == 0) return new int[]{-1, -1};
int left = 0, workdaysUsed = 0, maxStreak = 0;
int bestLeft = 0, bestRight = 0;
for (int right = 0; right < calendar.length; right++) {
if (calendar[right] == 'W') workdaysUsed++;
while (workdaysUsed > pto) {
if (calendar[left] == 'W') workdaysUsed--;
left++;
}
if (right - left + 1 > maxStreak) {
maxStreak = right - left + 1;
bestLeft = left;
bestRight = right;
}
}
return new int[]{bestLeft, bestRight};
}
// ──────────────────────────────────────────────────────────────────────────
// FOLLOW-UP B: Circular calendar (year wraps around)
// Trick: double the array, run sliding window, cap window at n.
// Time: O(n) | Space: O(n)
// ──────────────────────────────────────────────────────────────────────────
public static int longestVacationCircular(char[] calendar, int pto) {
int n = calendar.length;
if (n == 0) return 0;
// Count total workdays — if pto covers all, entire year is vacation
int totalW = 0;
for (char c : calendar) if (c == 'W') totalW++;
if (pto >= totalW) return n;
// Double the array to simulate wrap-around
char[] doubled = new char[2 * n];
for (int i = 0; i < 2 * n; i++) doubled[i] = calendar[i % n];
int left = 0, workdaysUsed = 0, maxStreak = 0;
for (int right = 0; right < 2 * n; right++) {
if (doubled[right] == 'W') workdaysUsed++;
while (workdaysUsed > pto || right - left + 1 > n) {
if (doubled[left] == 'W') workdaysUsed--;
left++;
}
maxStreak = Math.max(maxStreak, right - left + 1);
}
return maxStreak;
}
public static void main(String[] args) {
// =====================================================================
// TESTS
// =====================================================================
System.out.println("\n=== Problem : Longest Vacation ===\n");
// --- Original example ---
System.out.println("[Original]");
check("cal=[W,H,H,W,W,H,W] pto=2", longestVacation(new char[]{'W', 'H', 'H', 'W', 'W', 'H', 'W'}, 2), 5);
// --- Edge: all holidays ---
System.out.println("\n[Edge: all holidays]");
check("cal=[H,H,H,H] pto=0", longestVacation(new char[]{'H', 'H', 'H', 'H'}, 0), 4);
check("cal=[H,H,H,H] pto=3", longestVacation(new char[]{'H', 'H', 'H', 'H'}, 3), 4);
// --- Edge: all workdays ---
System.out.println("\n[Edge: all workdays]");
check("cal=[W,W,W,W] pto=0", longestVacation(new char[]{'W', 'W', 'W', 'W'}, 0), 0);
check("cal=[W,W,W,W] pto=2", longestVacation(new char[]{'W', 'W', 'W', 'W'}, 2), 2);
check("cal=[W,W,W,W] pto=4", longestVacation(new char[]{'W', 'W', 'W', 'W'}, 4), 4);
// --- Edge: single day ---
System.out.println("\n[Edge: single day]");
check("cal=[H] pto=0", longestVacation(new char[]{'H'}, 0), 1);
check("cal=[W] pto=0", longestVacation(new char[]{'W'}, 0), 0);
check("cal=[W] pto=1", longestVacation(new char[]{'W'}, 1), 1);
// --- Edge: empty / null ---
System.out.println("\n[Edge: empty / null]");
check("cal=[] pto=5", longestVacation(new char[]{}, 5), 0);
check("cal=null pto=5", longestVacation(null, 5), 0);
// --- Edge: pto exceeds total workdays (entire calendar) ---
System.out.println("\n[Edge: pto >= total workdays]");
check("cal=[W,H,W,H] pto=10", longestVacation(new char[]{'W', 'H', 'W', 'H'}, 10), 4);
// --- Edge: alternating pattern ---
System.out.println("\n[Edge: alternating]");
check("cal=[W,H,W,H,W,H,W,H,W] pto=3", longestVacation(new char[]{'W', 'H', 'W', 'H', 'W', 'H', 'W', 'H', 'W'}, 3), 7);
// --- Edge: holidays at edges ---
System.out.println("\n[Edge: holidays at start/end]");
check("cal=[H,H,W,W,W,H,H] pto=1", longestVacation(new char[]{'H', 'H', 'W', 'W', 'W', 'H', 'H'}, 1), 3);
// --- Follow-up 2A: return range ---
System.out.println("\n[Follow-up: Return indices]");
int[] range = longestVacationRange(new char[]{'W', 'H', 'H', 'W', 'W', 'H', 'W'}, 2);
System.out.println(" range for [W,H,H,W,W,H,W] pto=2 → [" + range[0] + "," + range[1] + "]");
// --- Follow-up 2B: circular calendar ---
System.out.println("\n[Follow-up: Circular calendar]");
// [H,W,W,H] pto=1 → linear best = 2 (idx 0-1 or 3-3), circular wraps 3→0 = H,H,W = 3
check("circular [H,W,W,H] pto=1", longestVacationCircular(new char[]{'H', 'W', 'W', 'H'}, 1), 3);
check("circular [W,H,H,W] pto=1", longestVacationCircular(new char[]{'W', 'H', 'H', 'W'}, 1), 3);
// =====================================================================
// SUMMARY
// =====================================================================
System.out.println("\n══════════════════════════════════════");
System.out.printf("Results: %d passed, %d failed%n", passed, failed);
System.out.println("══════════════════════════════════════");
}
// ──────────────────────────────────────────────────────────────────────────
// TEST HARNESS — original examples + edge cases
// ──────────────────────────────────────────────────────────────────────────
static int passed = 0, failed = 0;
static void check(String label, int actual, int expected) {
if (actual == expected) {
passed++;
System.out.println(" ✓ " + label + " = " + actual);
} else {
failed++;
System.out.println(" ✗ " + label + " = " + actual + " (expected " + expected + ")");
}
}
static void checkException(String label, Runnable r) {
try { r.run(); failed++; System.out.println(" ✗ " + label + " — no exception thrown"); }
catch (IllegalArgumentException e) { passed++; System.out.println(" ✓ " + label + " — threw: " + e.getMessage()); }
}
}
Followup FAQs
Q: "Return the actual start and end indices?"
A: Track bestLeft/bestRight whenever maxStreak is updated.
(Implemented above as longestVacationRange.)
Q: "What if the calendar is circular (wraps around)?"
A: Double the array, run sliding window with max window size n.
(Implemented above as longestVacationCircular.)
Q: "What if PTO days have variable cost (some days cost 2 PTO)?"
A: Replace the counter with a running sum. The window condition becomes
sum <= pto_budget instead of count <= pto.
Q: "What if there are multiple day types (H, W, half-day)?"
A: Assign each type a PTO cost (H=0, half=0.5, W=1) and use the
variable-cost sliding window above.
Q: "Why sliding window and not DP?"
A: DP would be O(n * pto) time and O(n) space. Sliding window exploits
the monotonicity of the "workdays used" count to achieve O(n) time
and O(1) space — strictly better.