Minimum Penalty for a Shop

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

1. 1Build 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.
2. 2Scan 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.
3. 3Compute prefixN[j] + suffixY at each j and compare it with the best penalty seen so far, because every legal closing hour must be considered.
4. 4Update 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.
5. 5After 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.
6. 6Start 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

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

#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.

#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.

Common mistakesthe boundary and tie rules are easy to invert