# Minimum Penalty for a Shop
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-penalty-for-a-shop)
Canonical: https://scaleengineer.com/dsa/problems/minimum-penalty-for-a-shop
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** String
**Companies:** [Stripe](https://scaleengineer.com/companies/stripe)
---
## Problem
You are given the customer visit log of a shop represented by a **0-indexed** string `customers` consisting only of characters `'N'` and `'Y'`:

* if the `ith` character is `'Y'`, it means that customers come at the `ith` hour
* whereas `'N'` indicates that no customers come at the `ith` hour.

If the shop closes at the `jth` hour (`0 <= j <= n`), the **penalty** is calculated as follows:

* For every hour when the shop is open and no customers come, the penalty increases by `1`.
* For every hour when the shop is closed and customers come, the penalty increases by `1`.

Return _the **earliest** hour at which the shop must be closed to incur a **minimum** penalty._

**Note** that if a shop closes at the `jth` hour, it means the shop is closed at the hour `j`.

**Example 1:**

**Input:** customers = "YYNY"
**Output:** 2
**Explanation:** 
- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.
- Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.
- Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.
- Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.
- Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty.
Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.

**Example 2:**

**Input:** customers = "NNNNN"
**Output:** 0
**Explanation:** It is best to close the shop at the 0th hour as no customers arrive.

**Example 3:**

**Input:** customers = "YYYY"
**Output:** 4
**Explanation:** It is best to close the shop at the 4th hour as customers arrive at each hour.

**Constraints:**

* `1 <= customers.length <= 105`
* `customers` consists only of characters `'Y'` and `'N'`.

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. It iterates through every possible closing hour `j` from `0` to `n` (where `n` is the number of hours). For each potential closing hour, it calculates the total penalty by scanning the `customers` string.
**Time:** O(n^2), where n is the length of the `customers` string. The outer loop runs `n+1` times, and the inner loops for calculating penalty take O(n) time in each iteration. · **Space:** O(1), as we only use a few variables to store the state, regardless of the input size.
**Pros:** Simple to understand and implement.; Directly follows the problem definition without complex logic.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on platforms with large test cases.
### Explanation
The algorithm considers each hour `j` from `0` to `n` as a potential closing time. For a given `j`, the shop is open from hour `0` to `j-1` and closed from hour `j` to `n-1`. The penalty is calculated by summing the number of 'N's during open hours and the number of 'Y's during closed hours. This calculation is performed from scratch for every possible closing hour. The algorithm keeps track of the minimum penalty found so far and the earliest hour `j` that yields this minimum.

```java
class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        int minPenalty = Integer.MAX_VALUE;
        int bestHour = -1;

        for (int j = 0; j <= n; j++) {
            int currentPenalty = 0;
            // Penalty for open hours (0 to j-1)
            for (int i = 0; i < j; i++) {
                if (customers.charAt(i) == 'N') {
                    currentPenalty++;
                }
            }
            // Penalty for closed hours (j to n-1)
            for (int i = j; i < n; i++) {
                if (customers.charAt(i) == 'Y') {
                    currentPenalty++;
                }
            }

            if (currentPenalty < minPenalty) {
                minPenalty = currentPenalty;
                bestHour = j;
            }
        }
        return bestHour;
    }
}
```
### Algorithm
- Initialize `minPenalty` to a very large value and `bestHour` to 0.
- Iterate through each possible closing hour `j` from `0` to `n` (where `n` is the length of `customers`).
- For each `j`, calculate the `currentPenalty`:
  - Initialize `currentPenalty` to 0.
  - Iterate from `i = 0` to `j-1`. If `customers.charAt(i)` is 'N', increment `currentPenalty`.
  - Iterate from `i = j` to `n-1`. If `customers.charAt(i)` is 'Y', increment `currentPenalty`.
- If `currentPenalty` is less than `minPenalty`, update `minPenalty` to `currentPenalty` and `bestHour` to `j`.
- After checking all possible hours, return `bestHour`.

## Using Prefix and Suffix Sums
This approach optimizes the penalty calculation by pre-computing the counts of 'N's and 'Y's. The penalty for closing at hour `j` is the sum of 'N's before `j` and 'Y's at or after `j`. We can use a prefix sum array for the 'N's and a suffix sum array for the 'Y's to find these counts in O(1) time for each `j`.
**Time:** O(n). We perform three separate passes over the data: one for `prefixN`, one for `suffixY`, and one to find the minimum penalty. Each pass takes O(n) time. · **Space:** O(n). We use two extra arrays of size `n+1` to store the prefix and suffix counts.
**Pros:** Much more efficient than the brute-force approach.; Linear time complexity is well within the given constraints.
**Cons:** Requires extra space proportional to the input size, which might be a concern for very large inputs in a memory-constrained environment.
### Explanation
The core idea is to avoid re-calculating counts for each closing hour. We create a `prefixN` array where `prefixN[i]` stores the total number of 'N's in the substring `customers[0...i-1]`. We also create a `suffixY` array where `suffixY[i]` stores the total number of 'Y's in the substring `customers[i...n-1]`. Both arrays can be computed in O(n) time. Once we have these arrays, the penalty for closing at hour `j` can be calculated in O(1) time as `penalty(j) = prefixN[j] + suffixY[j]`. We then iterate from `j = 0` to `n`, calculate the penalty for each `j` using the pre-computed arrays, and find the hour with the minimum penalty.

```java
class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        
        int[] prefixN = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixN[i + 1] = prefixN[i] + (customers.charAt(i) == 'N' ? 1 : 0);
        }

        int[] suffixY = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixY[i] = suffixY[i + 1] + (customers.charAt(i) == 'Y' ? 1 : 0);
        }

        int minPenalty = Integer.MAX_VALUE;
        int bestHour = -1;
        for (int j = 0; j <= n; j++) {
            int currentPenalty = prefixN[j] + suffixY[j];
            if (currentPenalty < minPenalty) {
                minPenalty = currentPenalty;
                bestHour = j;
            }
        }
        return bestHour;
    }
}
```
### Algorithm
- Create a `prefixN` array of size `n+1`. Populate it such that `prefixN[i]` is the count of 'N's in `customers` up to index `i-1`.
- Create a `suffixY` array of size `n+1`. Populate it such that `suffixY[i]` is the count of 'Y's in `customers` from index `i` to the end.
- Initialize `minPenalty` to a large value and `bestHour` to 0.
- Iterate `j` from `0` to `n`.
- For each `j`, calculate `currentPenalty = prefixN[j] + suffixY[j]`.
- If `currentPenalty` is less than `minPenalty`, update `minPenalty` to `currentPenalty` and `bestHour` to `j`.
- Return `bestHour`.

## Single Pass with Constant Space
This is the most optimal approach. It builds upon the idea that the penalty for closing at hour `j+1` can be derived from the penalty for closing at hour `j` with a simple adjustment. This allows us to calculate the penalties for all closing hours in a single pass through the `customers` string, without needing extra arrays.
**Time:** O(n). We have an initial pass to count 'Y's (which can be combined into one loop) and then a single loop through the string, resulting in linear time complexity. · **Space:** O(1). We only use a few variables to keep track of the current penalty, minimum penalty, and best hour, regardless of the input size.
**Pros:** Optimal solution with linear time and constant space complexity.; Highly efficient for very large inputs.
**Cons:** The logic for updating the penalty might be slightly less intuitive than the prefix/suffix sum approach at first glance.
### Explanation
We can analyze the change in penalty when moving the closing time from hour `j` to `j+1`. The only hour that changes its state (from closed to open) is hour `j`. If `customers.charAt(j) == 'Y'`, the penalty decreases by 1. If `customers.charAt(j) == 'N'`, the penalty increases by 1. This gives us the relation: `penalty(j+1) = penalty(j) + (customers.charAt(j) == 'N' ? 1 : -1)`. The algorithm starts by calculating the initial penalty for closing at hour 0 (total 'Y's). Then, it iterates from `j = 1` to `n`, updating the `currentPenalty` using the rule above and tracking the minimum penalty and corresponding hour.

```java
class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        // Calculate initial penalty for closing at hour 0 (all hours are closed)
        // This is simply the count of all 'Y's.
        int currentPenalty = 0;
        for (char c : customers.toCharArray()) {
            if (c == 'Y') {
                currentPenalty++;
            }
        }

        int minPenalty = currentPenalty;
        int bestHour = 0;

        // Iterate through all possible closing hours from 1 to n
        for (int j = 1; j <= n; j++) {
            // Adjust penalty based on the customer at hour j-1, which is now open
            char customer = customers.charAt(j - 1);
            if (customer == 'Y') {
                currentPenalty--; // This hour is now open, so we lose a penalty point
            } else { // customer == 'N'
                currentPenalty++; // This hour is now open, so we gain a penalty point
            }

            if (currentPenalty < minPenalty) {
                minPenalty = currentPenalty;
                bestHour = j;
            }
        }
        return bestHour;
    }
}
```
### Algorithm
- Calculate the initial penalty for closing at hour 0. This is equal to the total count of 'Y's in the `customers` string.
- Initialize `minPenalty` with this initial penalty and `bestHour` to 0. Let `currentPenalty` also be this value.
- Iterate `j` from `1` to `n`. In each iteration, `j` represents the new closing hour.
- Update `currentPenalty` based on the character at `customers[j-1]`:
  - If `customers[j-1] == 'Y'`, decrement `currentPenalty`.
  - If `customers[j-1] == 'N'`, increment `currentPenalty`.
- If the new `currentPenalty` is strictly less than `minPenalty`, update `minPenalty = currentPenalty` and `bestHour = j`.
- Return `bestHour`.

# Solutions
### Java

```java
class Solution {
public
  int bestClosingTime(String customers) {
    int n = customers.length();
    int[] s = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + (customers.charAt(i) == 'Y' ? 1 : 0);
    }
    int ans = 0, cost = 1 << 30;
    for (int j = 0; j <= n; ++j) {
      int t = j - s[j] + s[n] - s[j];
      if (cost > t) {
        ans = j;
        cost = t;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int bestClosingTime(string customers) {
    int n = customers.size();
    vector<int> s(n + 1);
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + (customers[i] == 'Y');
    }
    int ans = 0, cost = 1 << 30;
    for (int j = 0; j <= n; ++j) {
      int t = j - s[j] + s[n] - s[j];
      if (cost > t) {
        ans = j;
        cost = t;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def bestClosingTime(self, customers: str) -> int: n = len(customers) s = [0] * (n + 1) for i, c in enumerate(customers): s[i + 1] = s[i] + int(c == 'Y') ans, cost = 0, inf for j in range(n + 1): t = j - s[j] + s[- 1] - s[j] if cost > t: ans, cost = j, t return ans

```