Minimum Penalty for a Shop

medium prefix sum sweep

Problem

A shop's day is described by a string customers of length n, where the i-th character is 'Y' if customers show up during hour i and 'N' if nobody does. You may close the shop at any hour j from 0 to n: hours 0..j−1 are open and hours j..n−1 are closed.

The penalty for closing at hour j is the number of open hours with no customers plus the number of closed hours when customers arrive. Return the earliest closing hour with the minimum penalty.

Inputcustomers = "YYNY"

Output2

Closing at hour 2 serves both 'Y' hours 0 and 1 and only misses the customers at hour 3, for a minimum penalty of 1.

customers (string of Y and N)

def best_closing_time(customers):
    penalty = customers.count("Y")    # close at hour 0
    best = penalty
    best_hour = 0
    for j, ch in enumerate(customers):
        if ch == "N":
            penalty += 1    # one more empty open hour
        else:
            penalty -= 1    # one less missed customer
        if penalty < best:
            best = penalty
            best_hour = j + 1
    return best_hour

function bestClosingTime(customers) {
  let penalty = 0;
  for (const ch of customers) if (ch === "Y") penalty++;
  let best = penalty, bestHour = 0;
  for (let j = 0; j < customers.length; j++) {
    penalty += customers[j] === "N" ? 1 : -1;
    if (penalty < best) {
      best = penalty;
      bestHour = j + 1;
    }
  }
  return bestHour;
}

int bestClosingTime(String customers) {
    int penalty = 0;
    for (char ch : customers.toCharArray()) if (ch == 'Y') penalty++;
    int best = penalty, bestHour = 0;
    for (int j = 0; j < customers.length(); j++) {
        penalty += customers.charAt(j) == 'N' ? 1 : -1;
        if (penalty < best) {
            best = penalty;
            bestHour = j + 1;
        }
    }
    return bestHour;
}

int bestClosingTime(string customers) {
    int penalty = 0;
    for (char ch : customers) if (ch == 'Y') penalty++;
    int best = penalty, bestHour = 0;
    for (int j = 0; j < (int)customers.size(); j++) {
        penalty += customers[j] == 'N' ? 1 : -1;
        if (penalty < best) {
            best = penalty;
            bestHour = j + 1;
        }
    }
    return bestHour;
}

Explanation

The brute force recounts the penalty from scratch for each of the n+1 candidate closing hours, which is O(n²). The key insight is that moving the closing hour one step later changes the penalty by exactly ±1, so a single sweep with a running count — the prefix-sum idea — evaluates every candidate.

We seed the sweep with the easiest candidate: closing at hour 0 keeps the shop shut all day, so every 'Y' hour is a missed customer and the penalty is simply the count of 'Y' in the string.

Now slide the closing hour from j to j+1. The only hour that changes status is hour j, which flips from closed to open. If hour j is 'Y', those customers are now served instead of missed, so the penalty drops by 1. If it is 'N', the shop now sits open through an empty hour, so the penalty rises by 1. After each update we compare against the best so far, replacing it only on a strict improvement so the earliest minimum wins.

On the default example "YYNY" the penalties for closing hours 0..4 are 3, 2, 1, 2, 1. The minimum value 1 first appears at hour 2 (hour 4 ties later but is not earlier), so the answer is 2.

This is prefix sums in disguise: penalty(j) equals the number of 'N' in the prefix [0, j) plus the number of 'Y' in the suffix [j, n). Rather than building both arrays, the sweep maintains their sum incrementally — one pass, two integers.

The seed count is O(n) and the sweep touches each hour once with O(1) work, so the total time is O(n) with O(1) extra space.

Time: O(n) Space: O(1)