Back to solutions

Minimum Penalty for a Shop

MediumArrays

Find the closing hour that minimizes penalty from a customer log.

Open problem
Constraints
  • 1 <= length <= 10^5
  • characters are 'Y' or 'N'

Running penalty delta

Time O(n)Space O(1)

Start with the penalty of closing at hour 0, which is just the total number of 'Y' (all of them are lost). Move the closing time forward one hour at a time: an open 'Y' hour removes one penalty, an open 'N' hour adds one. Track the running penalty and remember the earliest hour with the smallest value.

Key terms
penalty:
Lost customers: 'N' hours while open plus 'Y' hours after closing.
incremental update:
Adjusting the penalty by a small delta as the closing hour advances rather than recomputing.
int bestClosingTime(const string& customers) {
    int penalty = count(customers.begin(), customers.end(), 'Y');
    int best = penalty, bestHour = 0, cur = penalty;
    for (int j = 0; j < (int)customers.size(); j++) {
        cur += customers[j] == 'Y' ? -1 : 1;
        if (cur < best) { best = cur; bestHour = j + 1; }
    }
    return bestHour;
}
Step by step
  1. Compute the penalty for closing at hour 0 = total count of 'Y'.
  2. For each hour j, update: subtract 1 if customers[j] is 'Y' (now open and served), add 1 if 'N'.
  3. After processing hour j, the running value is the penalty of closing at hour j+1.
  4. Track the minimum penalty and the earliest hour achieving it; return that hour.