Unoccupied Computers

Problem Understanding

A cafe has n computers.

Customers are represented by uppercase English letters in a string s.

Each customer appears exactly twice:

• First occurrence → customer arrives.

• Second occurrence → customer leaves.

When a customer arrives:

• If a computer is available, they get one.

• If no computer is available, they are rejected.

We need to find:

How many customers were rejected because no computer was available?

Why is this problem tricky?

At first, it may seem enough to check whether a character has appeared before.

But there is an important situation:

A customer who was rejected does not have a computer, so when their second occurrence appears, we must not free a computer.

For example:

n = 2
s = "CDEBADCABE"

Let's see what happens.

Therefore:

Answer = 3

The rejected customers are:

E, B, A

The Main Idea

We can maintain the status of every customer using an integer array:

int[] status = new int[26];

Why 26?

Because there are only 26 uppercase English letters:

A B C D ... Z

We use three states:

0 → Customer has not arrived yet
1 → Customer got a computer
2 → Customer was rejected

For example:

status['A' - 'A'] = 1;

means customer A currently has a computer.

And:

status['B' - 'A'] = 2;

means customer B was rejected.

Converting Character to Array Index

Since Java arrays use indexes from 0 to 25, we convert the character:

int index = c - 'A';

For example:

'A' - 'A' = 0
'B' - 'A' = 1
'C' - 'A' = 2
'D' - 'A' = 3

So:

status[index]

stores the status of that customer.

Complete Code

class Solution {
    public int solve(int n, String s) {
        int[] status = new int[26];

        int available = n;
        int rejected = 0;

        for (char c : s.toCharArray()) {
            int index = c - 'A';

            if (status[index] == 0) {
                // First occurrence: customer arrives

                if (available > 0) {
                    // Computer available
                    status[index] = 1;
                    available--;
                } else {
                    // No computer available
                    status[index] = 2;
                    rejected++;
                }
            } 
            else if (status[index] == 1) {
                // Customer who got a computer is leaving

                status[index] = 0;
                available++;
            } 
            else {
                // Customer was rejected earlier
                // So they do not have a computer

                status[index] = 0;
            }
        }

        return rejected;
    }
}

Understanding Each Variable

status

int[] status = new int[26];

Stores the current state of every customer.

Possible values:

0 → Not arrived
1 → Has computer
2 → Rejected

available

int available = n;

Stores how many computers are currently free.

Initially, all n computers are available.

For example:

n = 3

available = 3

When someone gets a computer:

available--;

When a customer who had a computer leaves:

available++;

rejected

int rejected = 0;

Counts customers who arrive when there are no computers available.

When that happens:

rejected++;

First Occurrence

This condition:

if (status[index] == 0)

means this is the customer's first occurrence.

Now we check:

if (available > 0)

Computer available

Give the customer a computer:

status[index] = 1;
available--;

For example:

Before:
available = 2

Customer A arrives.

After:
status[A] = 1
available = 1

No computer available

The customer is rejected:

status[index] = 2;
rejected++;

For example:

available = 0

Customer B arrives.

status[B] = 2
rejected = 1

Notice that we do not decrease available, because the rejected customer didn't receive a computer.

Second Occurrence of a Successful Customer

Suppose:

status[index] == 1

This means the customer previously received a computer.

Therefore, this occurrence represents their departure.

We release the computer:

status[index] = 0;
available++;

Example:

Customer C has computer.

available = 0

C leaves.

available = 1

Second Occurrence of a Rejected Customer

This is the most important part.

Suppose:

status[index] == 2

This means the customer was rejected earlier.

They never had a computer.

Therefore, when they appear for the second time, we must not increase available.

We simply reset:

status[index] = 0;

This is what fixes the wrong answer from the previous solution.

Dry Run

Let's use:

n = 2
s = "CDEBADCABE"

Initial state:

available = 2
rejected = 0

C arrives

Computer available.

status[C] = 1
available = 1

D arrives

Computer available.

status[D] = 1
available = 0

E arrives

No computer.

status[E] = 2
rejected = 1

B arrives

No computer.

status[B] = 2
rejected = 2

A arrives

No computer.

status[A] = 2
rejected = 3

D leaves

D had a computer.

status[D] = 0
available = 1

C leaves

C had a computer.

status[C] = 0
available = 2

A appears again

A was rejected.

status[A] = 0
available = 2

Important: We don't do available++.

B appears again

B was rejected.

status[B] = 0
available = 2

E appears again

E was rejected.

status[E] = 0
available = 2

Final result:

rejected = 3

Why the Previous Code Failed

The incorrect logic essentially treated every second occurrence as:

available++;

But consider:

E → rejected
...
E → second occurrence

E never received a computer.

So E cannot possibly free a computer.

That's why we need to distinguish:

Got computer → status = 1
Rejected      → status = 2

This three-state approach is the key to solving the problem correctly.

Complexity

The string contains at most 52 characters.

We process every character exactly once.

Time Complexity

O(|s|)

Auxiliary Space

The array has only 26 elements:

int[] status = new int[26];

Therefore:

O(26) = O(1)

So the solution satisfies the expected complexity:

Time  → O(|s|)
Space → O(1)

Easy Way to Remember the Logic

Think of the three states like this:

0 = Not seen
1 = Got computer
2 = Rejected

Then:

First occurrence
       |
       v
   Is status 0?
       |
    Yes
       |
       v
Is computer available?
   /           \
 Yes            No
  |              |
  v              v
status = 1    status = 2
available--   rejected++

For the second occurrence:

status = 1
   |
   v
Customer had computer
   |
   v
Release computer

But:

status = 2
   |
   v
Customer was rejected
   |
   v
Do NOT release computer

Final takeaway

The most important concept in this problem is:

Don't just track whether a customer appeared. Track whether they actually received a computer.

That distinction is what makes the solution pass all test cases.