Unoccupied Computers

Problem Overview

Each uppercase letter appears exactly twice: first arrival, then departure.

Intuition

Each uppercase letter appears exactly twice: first arrival, then departure. There are n computers. On first sight of a customer, seat them if a machine is free; otherwise they walk away. On second sight, they leave and free a seat only if they were seated. Count how many first visits happen when no computer is available.

Algorithm

1Keep state per letter: 0 absent, 1 inside without seat, 2 seated.
2Scan the string left to right.
3First visit: if a computer is free, take one and mark seated; else increment walkaways and mark waiting.
4Second visit: if seated, release a computer; reset state to absent.
5Return the walkaway count.

Example Walkthrough

Input: n = 2, s = "ABACBE"

1. A arrives and takes a seat (1 free left).
2. B arrives and takes the last seat.
3. C arrives with no seats and walks away.
4. Later departures free machines for following arrivals.

Output: 1

Common Pitfalls

• Only decrement available computers when the departing customer was seated.
• Walkaways still need a second letter in the log; their state is waiting, not absent until leave.
• Use a byte or int state array, not ad hoc char markers that confuse arrival and departure.
• n is the computer count, not the string length.

Unoccupied Computers.java

Java

// Approach: Each letter appears twice (arrive, leave). Track per customer:
// absent, waiting without a seat, or seated. On first sight, seat if a computer
// is free else count a walk-away. On second sight, free a seat only if seated.
// Complexity: O(|s|) time and O(1) extra space.
class Solution {

    public int solve(int n, String s) {
        byte[] state = new byte[26];
        int walkaways = 0;

        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'A';

            if (state[idx] == 0) {
                if (n > 0) {
                    n--;
                    state[idx] = 2;
                } else {
                    walkaways++;
                    state[idx] = 1;
                }
            } else {
                if (state[idx] == 2) {
                    n++;
                }
                state[idx] = 0;
            }
        }

        return walkaways;
    }
}

Was this solution helpful?