Minimum Penalty for a Shop

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

Examples

Example 1

1
2
3
4
5
6
7
8
9
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

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

Example 3

1
2
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 <= 10^5
customers consists only of characters 'Y' and 'N'.

Solution

Method 1 – Prefix Sum for Penalty Calculation

Intuition

For each possible closing hour, calculate penalty: open hours with ‘N’ and closed hours with ‘Y’. Use prefix sums for efficient calculation.

Approach

Precompute prefix sums for ‘N’ and ‘Y’.
For each closing hour j (0 to n), penalty = count of ‘N’ in [0, j-1] + count of ‘Y’ in [j, n-1].
Track minimum penalty and earliest hour.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <string>
class Solution {
public:
    int bestClosingTime(std::string customers) {
        int n = customers.size(), penalty = 0, minPenalty = n+1, res = 0;
        for (char c : customers) if (c == 'Y') penalty++;
        int curr = penalty;
        for (int j = 0; j <= n; ++j) {
            if (curr < minPenalty) { minPenalty = curr; res = j; }
            if (j < n) curr += (customers[j] == 'N') - (customers[j] == 'Y');
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func bestClosingTime(customers string) int {
    n, penalty := len(customers), 0
    for _, c := range customers {
        if c == 'Y' { penalty++ }
    }
    minPenalty, res := penalty, 0
    curr := penalty
    for j := 0; j <= n; j++ {
        if curr < minPenalty { minPenalty, res = curr, j }
        if j < n {
            if customers[j] == 'N' { curr++ } else if customers[j] == 'Y' { curr-- }
        }
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length(), penalty = 0;
        for (char c : customers.toCharArray()) if (c == 'Y') penalty++;
        int minPenalty = penalty+1, res = 0, curr = penalty;
        for (int j = 0; j <= n; ++j) {
            if (curr < minPenalty) { minPenalty = curr; res = j; }
            if (j < n) curr += (customers.charAt(j) == 'N' ? 1 : -1);
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    fun bestClosingTime(customers: String): Int {
        var penalty = customers.count { it == 'Y' }
        var minPenalty = penalty+1
        var res = 0
        var curr = penalty
        for (j in 0..customers.length) {
            if (curr < minPenalty) { minPenalty = curr; res = j }
            if (j < customers.length) {
                curr += if (customers[j] == 'N') 1 else -1
            }
        }
        return res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def bestClosingTime(self, customers: str) -> int:
        penalty = customers.count('Y')
        min_penalty, res, curr = penalty+1, 0, penalty
        for j in range(len(customers)+1):
            if curr < min_penalty:
                min_penalty, res = curr, j
            if j < len(customers):
                curr += 1 if customers[j] == 'N' else -1
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn best_closing_time(customers: String) -> i32 {
        let n = customers.len();
        let bytes = customers.as_bytes();
        let mut penalty = bytes.iter().filter(|&&c|c==b'Y').count() as i32;
        let mut min_penalty = penalty+1;
        let mut res = 0;
        let mut curr = penalty;
        for j in 0..=n {
            if curr < min_penalty { min_penalty = curr; res = j as i32; }
            if j < n {
                curr += if bytes[j]==b'N' { 1 } else { -1 };
            }
        }
        res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    bestClosingTime(customers: string): number {
        let penalty = [...customers].filter(c=>c==='Y').length;
        let minPenalty = penalty+1, res = 0, curr = penalty;
        for (let j = 0; j <= customers.length; ++j) {
            if (curr < minPenalty) { minPenalty = curr; res = j; }
            if (j < customers.length) {
                curr += customers[j] === 'N' ? 1 : -1;
            }
        }
        return res;
    }
}

Complexity

⏰ Time complexity: O(n) — Single pass.
🧺 Space complexity: O(1) — Only variables.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Prefix Sum for Penalty Calculation#

Intuition#

Approach#

Code#

Complexity#