Number of customers who could not get a computer

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}