Minimum Penalty for a Shop — Editorial

Opening the reading…

Intuitionthe closing hour splits the string into two independently counted regions

A closing hour j creates two regions: hours 0 through j - 1 remain open, while hours j through n - 1 are closed. An N in the first region costs one because the shop stayed open without a customer. A Y in the second region costs one because the shop was closed when a customer arrived. The penalty is exactly the sum of those two counts.

This turns the problem into evaluating every boundary from 0 to n. For each boundary, you need the number of N characters on its left and the number of Y characters on its right. A prefix count supplies the first value, and a suffix count supplies the second. Scanning boundaries in reverse keeps the suffix count available without building a second array; accepting equal penalties while scanning right to left preserves the earliest hour.

Approach

Build prefixN so prefixN[j] equals the number of N characters in indices 0 through j - 1, because those are precisely the open hours when the shop closes at j.

Scan possible closing hours from n down to 0 while maintaining suffixY, the number of Y characters in indices j through n - 1, because that is the closed-hours contribution at the current boundary.

Compute prefixN[j] + suffixY at each j and compare it with the best penalty seen so far, because every legal closing hour must be considered.

Update the answer when the new penalty is less than or equal to the current minimum, because reverse scanning encounters later hours first and replacing on ties leaves the smaller, earlier hour stored at the end.

After evaluating j, add customers[j - 1] to suffixY when that character is Y, because it belongs to the suffix for the next boundary j - 1 but not to the suffix for the boundary just evaluated.

Start with bestHour = n and minPenalty = n, because closing at any boundary can classify at most n hours as penalty-producing and hour n is a valid initial answer.

Complexityfor the prefix-array solution

MEASURE	BOUND	WHY
Time	O(n)	The prefix construction visits each character once, and the boundary scan evaluates n + 1 positions with constant work at each one. The two passes are sequential rather than nested, so their costs add to O(n).
Space	O(n)	prefixN stores one count for every boundary from 0 to n. The scalar suffix count and answer variables use O(1) additional space. The returned integer is required output and is excluded; the working bound stays O(n) for every input shape.

Here n is the length of customers.

Annotated solutionC++ · prefix counts plus a reverse suffix scan

CPPEvaluate every boundary with a prefix count of N and a reverse-maintained suffix count of Y.

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int bestClosingTime(string customers) {
        int n = static_cast<int>(customers.size());
        vector<int> prefixN(n + 1, 0);

        for (int i = 0; i < n; ++i) {
            prefixN[i + 1] = prefixN[i] + (customers[i] == 'N' ? 1 : 0);
        }

        int suffixY = 0;
        int minPenalty = n;
        int bestHour = n;

        for (int j = n; j >= 0; --j) {
            int penalty = prefixN[j] + suffixY;
            if (penalty <= minPenalty) {
                minPenalty = penalty;
                bestHour = j;
            }

            if (j > 0 && customers[j - 1] == 'Y') {
                ++suffixY;
            }
        }

        return bestHour;
    }
};

The order inside the reverse loop is the key detail. At the start of iteration j, suffixY represents indices j through n - 1, so the penalty is correct only before adding customers[j - 1]. The update then prepares the count for boundary j - 1. The less-than-or-equal comparison is equally deliberate: reverse scanning sees larger hours first, so a tie must replace the stored answer with the smaller current hour.

The one-pass alternativean O(1)-space optimisation

You can avoid prefixN by starting with the penalty for closing at hour 0. At that boundary every Y is in the closed region, so the initial penalty is the total number of Y characters. Moving the boundary from j to j + 1 changes only customers[j]: an N becomes correctly open and adds one penalty, while a Y stops being incorrectly closed and removes one penalty.

CPPUpdate the current penalty when the boundary crosses one character, using constant extra space.

#include <string>
using namespace std;

class Solution {
public:
    int bestClosingTime(string customers) {
        int penalty = 0;
        for (char customer : customers) {
            if (customer == 'Y') {
                ++penalty;
            }
        }

        int bestPenalty = penalty;
        int bestHour = 0;

        for (int j = 0; j < static_cast<int>(customers.size()); ++j) {
            if (customers[j] == 'Y') {
                --penalty;
            } else {
                ++penalty;
            }

            if (penalty < bestPenalty) {
                bestPenalty = penalty;
                bestHour = j + 1;
            }
        }

        return bestHour;
    }
};

This is a genuine optimisation, not merely a different arrangement. It still takes O(n) time, but its extra space falls from O(n) to O(1) because it stores only the current penalty and best answer. The strict comparison is correct here because the scan moves from smaller hours to larger hours: keeping the first occurrence of a minimum automatically keeps the earliest closing hour.