Number of customers who could not get a computer
Problem
A café has n computers. The string lists events: the first time a letter appears, that customer arrives; the second time, they leave. An arriving customer takes a free computer, or leaves without one if all are busy (and their later departure changes nothing). Return how many customers could not get a computer.
Example 1
Input: n = 2, "ABBAJJKZKZ" Output: 0
Example 2
Input: n = 3, "GACCBDDBAGEE" Output: 1
D arrives while G, A and B hold all three computers.
Also asked as: Function to find Number of customers who could not get a computer
Test cases
Case 1
Input: "ABBAJJKZKZ", 2 Expected: 0
Case 2
Input: "GACCBDDBAGEE", 3 Expected: 1
Case 3
Input: "GACCBGDDBAEE", 3 Expected: 0
Case 4
Input: "GACCBDDBAGEE", 1 Expected: 4
Case 5
Input: "ABCBCA", 1 Expected: 2
View solutionHide solution1 approach
1. Simulate seats with a set
Time O(n)Space O(seats)
First time a customer id appears they take a seat (if one is free, else they walk away). Second appearance frees the seat.
function turnedAway(seq, k) { const seated = new Set(); const walkedAway = new Set(); let turned = 0; for (const id of seq) { if (seated.has(id)) seated.delete(id); // leaving else if (walkedAway.has(id)) walkedAway.delete(id); // second visit after being turned away else if (seated.size < k) seated.add(id); // gets a seat else { turned++; walkedAway.add(id); } // no seat } return turned;}