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

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 <= 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

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

Code

C++

#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;
    }
};

Go

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
}

Java

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;
    }
}

Kotlin

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
    }
}

Python

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

Rust

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
    }
}

TypeScript

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.