239. Number of Customers Who Could Not Get a Computer

A shop has N computers. A sequence of events is given as a string s in which every character (each representing one customer) appears exactly twice: a customer's first occurrence in s is their arrival, and their second occurrence is their departure, with all events happening strictly in the left-to-right order of s. On arrival, a customer is given a free computer if one is available (and keeps it until their departure); if none is available, they leave immediately and never use a computer at all. Print the total number of customers who never got a computer.

Input: The first line contains the integer N (number of computers). The second line contains the string s, where each character represents a customer and occurs exactly twice. Output: Print a single integer - the number of customers who never got a computer.

1 <= N <= 10^5, 2 <= |s| <= 2*10^5, every character of s occurs exactly twice

This is fundamentally a simulation problem, not really a 'clever algorithm' problem - the key skill being tested is careful, correct state tracking (occupied count, per-customer served status) rather than a specific data structure trick.

Simulate customers arriving and leaving a shop with a limited number of computers, and count how many customers left without ever getting one. Brute force: There isn't really a slower 'brute force' alternative here beyond directly simulating the events - the problem is inherently sequential (each event must be processed in order), so a single simulation pass is naturally both the simplest AND the correct approach. Optimised: Tracking, per customer, whether they were actually SERVED (not just whether they've been 'seen') is the crucial bookkeeping detail - it correctly distinguishes a real departure (freeing a computer) from a rejected customer's second appearance (which changes nothing), processed in one single linear pass through the event string.

Maintain an explicit array of N computer slots, each holding either 'free' or the identity of the customer currently occupying it. On every arrival, scan all N slots looking for a free one and occupy it, counting the customer as turned away if none is free; on every departure, scan all N slots to find the one occupied by that customer and free it. This directly models the physical setup described in the problem, but it pays an O(N) scan for essentially every event. Time: O(n*N) Space: O(N)

Recognize that the N computers are interchangeable, so there is no need to track which specific slot anyone uses, only how many are currently free. Keep a single integer counter of free computers and a hash set of customers currently seated. On arrival, decrement the counter and add the customer to the set if the counter is positive, otherwise count them as turned away; on departure, remove the customer from the set and increment the counter if they were in it, otherwise do nothing since they never got a computer. This drops the space usage down to only the number of distinct customers, independent of N. Time: O(n) Space: O(min(n, N))

Keep a stack of currently-free slot indices and a hashmap from customer to the specific slot they're occupying. On arrival, pop a slot index off the free stack in O(1) if one exists and record it in the hashmap, otherwise mark the customer as turned away; on departure, look up the customer's slot in O(1) and push it back onto the free stack. This still tracks which specific computer each customer uses, which the problem doesn't actually require, but it eliminates the linear scans of the brute-force approach. Time: O(n) Space: O(N)

1. Track how many computers are currently occupied, and remember (per customer) whether they successfully got one. 2. Scan the event string left to right: on a customer's FIRST appearance (arrival), if a computer is free, assign one and mark them as having gotten one; otherwise, they're rejected. 3. On a customer's SECOND appearance (departure), free up a computer ONLY if that customer had actually been assigned one earlier. 4. Count every customer who was rejected on arrival.

Time: O(|s|) - one single linear pass through the event string. Space: O(number of distinct customers), for tracking which customers were actually served.

N large enough that nobody is ever rejected (answer 0); N = 1 with many customers competing for the single computer; s up to 2*10^5 characters for performance.

Be explicit about the subtlety that a REJECTED customer's second appearance in the string is still just a character in s, but must NOT free up a computer - a common bug is treating every second-occurrence character as a genuine departure.