2483. Minimum Penalty for a Shop - Explanation

Description

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 i-th character is 'Y', it means that customers come at the i-th hour
whereas 'N' indicates that no customers come at the i-th hour.

If the shop closes at the j-th 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 j-th 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 <= 100,000
customers consists only of characters 'Y' and 'N'.

Topics

String Prefix Sum

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Prefix Sum - Used to precompute counts of characters before each position
Suffix Sum - Used to precompute counts of characters from each position onward
String Iteration - Processing characters sequentially while maintaining running totals
Greedy Optimization - Tracking the optimal answer while iterating through possible choices

1. Brute Force

Intuition

The shop can close at any hour from 0 to n (inclusive). If we close at hour i, we incur a penalty of 1 for each 'N' before hour i (shop was open but no customer) and 1 for each 'Y' from hour i onward (shop was closed but customer came). We try every possible closing time and pick the one with minimum penalty.

Algorithm

Initialize res and minPenalty to n (worst case).
For each possible closing hour i from 0 to n:
- Count 'N' characters in positions 0 to i-1 (penalty for being open when no one came).
- Count 'Y' characters in positions i to n-1 (penalty for being closed when customers came).
- If this total penalty is less than minPenalty, update minPenalty and res.
Return res.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        n = len(customers)
        res = n
        minPenalty = n

        for i in range(n + 1):
            penalty = 0
            for j in range(i):
                if customers[j] == 'N':
                    penalty += 1
            for j in range(i, n):
                if customers[j] == 'Y':
                    penalty += 1

            if penalty < minPenalty:
                minPenalty = penalty
                res = i

        return res

public class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        int res = n, minPenalty = n;

        for (int i = 0; i <= n; i++) {
            int penalty = 0;
            for (int j = 0; j < i; j++) {
                if (customers.charAt(j) == 'N') {
                    penalty++;
                }
            }
            for (int j = i; j < n; j++) {
                if (customers.charAt(j) == 'Y') {
                    penalty++;
                }
            }

            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }

        return res;
    }
}

class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size();
        int res = n, minPenalty = n;

        for (int i = 0; i <= n; i++) {
            int penalty = 0;
            for (int j = 0; j < i; j++) {
                if (customers[j] == 'N') {
                    penalty++;
                }
            }
            for (int j = i; j < n; j++) {
                if (customers[j] == 'Y') {
                    penalty++;
                }
            }

            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} customers
     * @return {number}
     */
    bestClosingTime(customers) {
        const n = customers.length;
        let res = n,
            minPenalty = n;

        for (let i = 0; i <= n; i++) {
            let penalty = 0;
            for (let j = 0; j < i; j++) {
                if (customers[j] === 'N') {
                    penalty++;
                }
            }
            for (let j = i; j < n; j++) {
                if (customers[j] === 'Y') {
                    penalty++;
                }
            }

            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }

        return res;
    }
}

public class Solution {
    public int BestClosingTime(string customers) {
        int n = customers.Length;
        int res = n, minPenalty = n;

        for (int i = 0; i <= n; i++) {
            int penalty = 0;
            for (int j = 0; j < i; j++) {
                if (customers[j] == 'N') {
                    penalty++;
                }
            }
            for (int j = i; j < n; j++) {
                if (customers[j] == 'Y') {
                    penalty++;
                }
            }

            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }

        return res;
    }
}

func bestClosingTime(customers string) int {
    n := len(customers)
    res, minPenalty := n, n

    for i := 0; i <= n; i++ {
        penalty := 0
        for j := 0; j < i; j++ {
            if customers[j] == 'N' {
                penalty++
            }
        }
        for j := i; j < n; j++ {
            if customers[j] == 'Y' {
                penalty++
            }
        }

        if penalty < minPenalty {
            minPenalty = penalty
            res = i
        }
    }

    return res
}

class Solution {
    fun bestClosingTime(customers: String): Int {
        val n = customers.length
        var res = n
        var minPenalty = n

        for (i in 0..n) {
            var penalty = 0
            for (j in 0 until i) {
                if (customers[j] == 'N') {
                    penalty++
                }
            }
            for (j in i until n) {
                if (customers[j] == 'Y') {
                    penalty++
                }
            }

            if (penalty < minPenalty) {
                minPenalty = penalty
                res = i
            }
        }

        return res
    }
}

class Solution {
    func bestClosingTime(_ customers: String) -> Int {
        let n = customers.count
        let chars = Array(customers)
        var res = n
        var minPenalty = n

        for i in 0...n {
            var penalty = 0
            for j in 0..<i {
                if chars[j] == "N" {
                    penalty += 1
                }
            }
            for j in i..<n {
                if chars[j] == "Y" {
                    penalty += 1
                }
            }

            if penalty < minPenalty {
                minPenalty = penalty
                res = i
            }
        }

        return res
    }
}

class Solution {
    /**
     * @param {string} customers
     * @return {number}
     */
    bestClosingTime(customers: string): number {
        const n: number = customers.length;
        let res: number = n,
            minPenalty: number = n;
        for (let i = 0; i <= n; i++) {
            let penalty: number = 0;
            for (let j = 0; j < i; j++) {
                if (customers[j] === 'N') {
                    penalty++;
                }
            }
            for (let j = i; j < n; j++) {
                if (customers[j] === 'Y') {
                    penalty++;
                }
            }
            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }
        return res;
    }
}

impl Solution {
    pub fn best_closing_time(customers: String) -> i32 {
        let s = customers.as_bytes();
        let n = s.len();
        let mut res = n as i32;
        let mut min_penalty = n as i32;

        for i in 0..=n {
            let mut penalty = 0;
            for j in 0..i {
                if s[j] == b'N' {
                    penalty += 1;
                }
            }
            for j in i..n {
                if s[j] == b'Y' {
                    penalty += 1;
                }
            }

            if penalty < min_penalty {
                min_penalty = penalty;
                res = i as i32;
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Prefix & Suffix

Intuition

Instead of recounting 'N' and 'Y' characters for each closing hour, we precompute prefix counts of 'N' and suffix counts of 'Y'. The prefix array tells us how many 'N' characters appear before each position, and the suffix array tells us how many 'Y' characters appear from each position onward. The penalty at any closing hour is simply the sum of these two precomputed values.

Algorithm

Build prefixN[i] = count of 'N' in positions 0 to i-1.
Build suffixY[i] = count of 'Y' in positions i to n-1.
For each closing hour i from 0 to n:
- Calculate penalty as prefixN[i] + suffixY[i].
- Track the minimum penalty and its corresponding hour.
Return the hour with minimum penalty.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        n = len(customers)
        cnt = 0

        prefixN = []
        for c in customers:
            prefixN.append(cnt)
            if c == 'N':
                cnt += 1
        prefixN.append(cnt)

        suffixY = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffixY[i] = suffixY[i + 1]
            if customers[i] == 'Y':
                suffixY[i] += 1

        res = n
        minPenalty = n
        for i in range(n + 1):
            penalty = prefixN[i] + suffixY[i]
            if penalty < minPenalty:
                minPenalty = penalty
                res = i

        return res

public class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        int cnt = 0;

        int[] prefixN = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixN[i] = cnt;
            if (customers.charAt(i) == 'N') {
                cnt++;
            }
        }
        prefixN[n] = cnt;

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

        int res = n, minPenalty = n;
        for (int i = 0; i <= n; i++) {
            int penalty = prefixN[i] + suffixY[i];
            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }

        return res;
    }
}

class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size(), cnt = 0;

        vector<int> prefixN(n + 1);
        for (int i = 0; i < n; i++) {
            prefixN[i] = cnt;
            if (customers[i] == 'N') {
                cnt++;
            }
        }
        prefixN[n] = cnt;

        vector<int> suffixY(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            suffixY[i] = suffixY[i + 1];
            if (customers[i] == 'Y') {
                suffixY[i]++;
            }
        }

        int res = n, minPenalty = n;
        for (int i = 0; i <= n; i++) {
            int penalty = prefixN[i] + suffixY[i];
            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} customers
     * @return {number}
     */
    bestClosingTime(customers) {
        const n = customers.length;
        let cnt = 0;

        const prefixN = [];
        for (const c of customers) {
            prefixN.push(cnt);
            if (c === 'N') {
                cnt++;
            }
        }
        prefixN.push(cnt);

        const suffixY = new Array(n + 1).fill(0);
        for (let i = n - 1; i >= 0; i--) {
            suffixY[i] = suffixY[i + 1];
            if (customers[i] === 'Y') {
                suffixY[i]++;
            }
        }

        let res = n,
            minPenalty = n;
        for (let i = 0; i <= n; i++) {
            const penalty = prefixN[i] + suffixY[i];
            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }

        return res;
    }
}

public class Solution {
    public int BestClosingTime(string customers) {
        int n = customers.Length;
        int cnt = 0;

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

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

        int res = n, minPenalty = n;
        for (int i = 0; i <= n; i++) {
            int penalty = prefixN[i] + suffixY[i];
            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }

        return res;
    }
}

func bestClosingTime(customers string) int {
    n := len(customers)
    cnt := 0

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

    suffixY := make([]int, n+1)
    for i := n - 1; i >= 0; i-- {
        suffixY[i] = suffixY[i+1]
        if customers[i] == 'Y' {
            suffixY[i]++
        }
    }

    res, minPenalty := n, n
    for i := 0; i <= n; i++ {
        penalty := prefixN[i] + suffixY[i]
        if penalty < minPenalty {
            minPenalty = penalty
            res = i
        }
    }

    return res
}

class Solution {
    fun bestClosingTime(customers: String): Int {
        val n = customers.length
        var cnt = 0

        val prefixN = IntArray(n + 1)
        for (i in 0 until n) {
            prefixN[i] = cnt
            if (customers[i] == 'N') {
                cnt++
            }
        }
        prefixN[n] = cnt

        val suffixY = IntArray(n + 1)
        for (i in n - 1 downTo 0) {
            suffixY[i] = suffixY[i + 1]
            if (customers[i] == 'Y') {
                suffixY[i]++
            }
        }

        var res = n
        var minPenalty = n
        for (i in 0..n) {
            val penalty = prefixN[i] + suffixY[i]
            if (penalty < minPenalty) {
                minPenalty = penalty
                res = i
            }
        }

        return res
    }
}

class Solution {
    func bestClosingTime(_ customers: String) -> Int {
        let n = customers.count
        let chars = Array(customers)
        var cnt = 0

        var prefixN = [Int](repeating: 0, count: n + 1)
        for i in 0..<n {
            prefixN[i] = cnt
            if chars[i] == "N" {
                cnt += 1
            }
        }
        prefixN[n] = cnt

        var suffixY = [Int](repeating: 0, count: n + 1)
        for i in stride(from: n - 1, through: 0, by: -1) {
            suffixY[i] = suffixY[i + 1]
            if chars[i] == "Y" {
                suffixY[i] += 1
            }
        }

        var res = n
        var minPenalty = n
        for i in 0...n {
            let penalty = prefixN[i] + suffixY[i]
            if penalty < minPenalty {
                minPenalty = penalty
                res = i
            }
        }

        return res
    }
}

class Solution {
    /**
     * @param {string} customers
     * @return {number}
     */
    bestClosingTime(customers: string): number {
        const n: number = customers.length;
        let cnt: number = 0;
        const prefixN: number[] = [];
        for (const c of customers) {
            prefixN.push(cnt);
            if (c === 'N') {
                cnt++;
            }
        }
        prefixN.push(cnt);
        const suffixY: number[] = new Array(n + 1).fill(0);
        for (let i = n - 1; i >= 0; i--) {
            suffixY[i] = suffixY[i + 1];
            if (customers[i] === 'Y') {
                suffixY[i]++;
            }
        }
        let res: number = n,
            minPenalty: number = n;
        for (let i = 0; i <= n; i++) {
            const penalty: number = prefixN[i] + suffixY[i];
            if (penalty < minPenalty) {
                minPenalty = penalty;
                res = i;
            }
        }
        return res;
    }
}

impl Solution {
    pub fn best_closing_time(customers: String) -> i32 {
        let s = customers.as_bytes();
        let n = s.len();
        let mut cnt = 0i32;

        let mut prefix_n = vec![0i32; n + 1];
        for i in 0..n {
            prefix_n[i] = cnt;
            if s[i] == b'N' {
                cnt += 1;
            }
        }
        prefix_n[n] = cnt;

        let mut suffix_y = vec![0i32; n + 1];
        for i in (0..n).rev() {
            suffix_y[i] = suffix_y[i + 1];
            if s[i] == b'Y' {
                suffix_y[i] += 1;
            }
        }

        let mut res = n as i32;
        let mut min_penalty = n as i32;
        for i in 0..=n {
            let penalty = prefix_n[i] + suffix_y[i];
            if penalty < min_penalty {
                min_penalty = penalty;
                res = i as i32;
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Iteration (Two Pass)

Intuition

We can avoid storing arrays by computing on the fly. First, count all 'Y' characters. This represents the penalty if we close at hour 0 (we miss all customers). Then iterate through the string: each 'Y' we pass reduces the penalty (we served them), and each 'N' we pass increases it (we were open for nothing). Track the minimum penalty as we go.

Algorithm

Count total 'Y' characters as cntY. Initialize minPenalty = cntY, res = 0, and cntN = 0.
Iterate through each character at index i:
- If it is 'Y', decrement cntY (one fewer missed customer).
- If it is 'N', increment cntN (one more wasted open hour).
- Calculate penalty as cntN + cntY.
- If penalty is less than minPenalty, update minPenalty and set res = i + 1.
Return res.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        cntY = sum(c == "Y" for c in customers)

        minPenalty = cntY
        res = cntN = 0
        for i, c in enumerate(customers):
            if c == "Y":
                cntY -= 1
            else:
                cntN += 1

            penalty = cntN + cntY
            if penalty < minPenalty:
                res = i + 1
                minPenalty = penalty

        return res

public class Solution {
    public int bestClosingTime(String customers) {
        int cntY = 0;
        for (char c : customers.toCharArray()) {
            if (c == 'Y') cntY++;
        }

        int minPenalty = cntY, res = 0, cntN = 0;
        for (int i = 0; i < customers.length(); i++) {
            if (customers.charAt(i) == 'Y') {
                cntY--;
            } else {
                cntN++;
            }

            int penalty = cntN + cntY;
            if (penalty < minPenalty) {
                res = i + 1;
                minPenalty = penalty;
            }
        }

        return res;
    }
}

class Solution {
public:
    int bestClosingTime(string customers) {
        int cntY = count(customers.begin(), customers.end(), 'Y');

        int minPenalty = cntY, res = 0, cntN = 0;
        for (int i = 0; i < customers.size(); i++) {
            if (customers[i] == 'Y') {
                cntY--;
            } else {
                cntN++;
            }

            int penalty = cntN + cntY;
            if (penalty < minPenalty) {
                res = i + 1;
                minPenalty = penalty;
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} customers
     * @return {number}
     */
    bestClosingTime(customers) {
        let cntY = 0;
        for (let c of customers) {
            if (c === 'Y') cntY++;
        }

        let minPenalty = cntY,
            res = 0,
            cntN = 0;
        for (let i = 0; i < customers.length; i++) {
            if (customers[i] === 'Y') {
                cntY--;
            } else {
                cntN++;
            }

            const penalty = cntN + cntY;
            if (penalty < minPenalty) {
                res = i + 1;
                minPenalty = penalty;
            }
        }

        return res;
    }
}

public class Solution {
    public int BestClosingTime(string customers) {
        int cntY = 0;
        foreach (char c in customers) {
            if (c == 'Y') cntY++;
        }

        int minPenalty = cntY, res = 0, cntN = 0;
        for (int i = 0; i < customers.Length; i++) {
            if (customers[i] == 'Y') {
                cntY--;
            } else {
                cntN++;
            }

            int penalty = cntN + cntY;
            if (penalty < minPenalty) {
                res = i + 1;
                minPenalty = penalty;
            }
        }

        return res;
    }
}

func bestClosingTime(customers string) int {
    cntY := 0
    for _, c := range customers {
        if c == 'Y' {
            cntY++
        }
    }

    minPenalty, res, cntN := cntY, 0, 0
    for i := 0; i < len(customers); i++ {
        if customers[i] == 'Y' {
            cntY--
        } else {
            cntN++
        }

        penalty := cntN + cntY
        if penalty < minPenalty {
            res = i + 1
            minPenalty = penalty
        }
    }

    return res
}

class Solution {
    fun bestClosingTime(customers: String): Int {
        var cntY = customers.count { it == 'Y' }

        var minPenalty = cntY
        var res = 0
        var cntN = 0
        for (i in customers.indices) {
            if (customers[i] == 'Y') {
                cntY--
            } else {
                cntN++
            }

            val penalty = cntN + cntY
            if (penalty < minPenalty) {
                res = i + 1
                minPenalty = penalty
            }
        }

        return res
    }
}

class Solution {
    func bestClosingTime(_ customers: String) -> Int {
        let chars = Array(customers)
        var cntY = chars.filter { $0 == "Y" }.count

        var minPenalty = cntY
        var res = 0
        var cntN = 0
        for i in 0..<chars.count {
            if chars[i] == "Y" {
                cntY -= 1
            } else {
                cntN += 1
            }

            let penalty = cntN + cntY
            if penalty < minPenalty {
                res = i + 1
                minPenalty = penalty
            }
        }

        return res
    }
}

class Solution {
    /**
     * @param {string} customers
     * @return {number}
     */
    bestClosingTime(customers: string): number {
        let cntY: number = 0;
        for (let c of customers) {
            if (c === 'Y') cntY++;
        }
        let minPenalty: number = cntY,
            res: number = 0,
            cntN: number = 0;
        for (let i = 0; i < customers.length; i++) {
            if (customers[i] === 'Y') {
                cntY--;
            } else {
                cntN++;
            }
            const penalty: number = cntN + cntY;
            if (penalty < minPenalty) {
                res = i + 1;
                minPenalty = penalty;
            }
        }
        return res;
    }
}

impl Solution {
    pub fn best_closing_time(customers: String) -> i32 {
        let s = customers.as_bytes();
        let mut cnt_y = s.iter().filter(|&&c| c == b'Y').count() as i32;

        let mut min_penalty = cnt_y;
        let mut res = 0i32;
        let mut cnt_n = 0i32;
        for i in 0..s.len() {
            if s[i] == b'Y' {
                cnt_y -= 1;
            } else {
                cnt_n += 1;
            }

            let penalty = cnt_n + cnt_y;
            if penalty < min_penalty {
                res = i as i32 + 1;
                min_penalty = penalty;
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

4. Iteration (One Pass)

Intuition

We can solve this in a single pass using a clever observation. Instead of tracking absolute penalty, we track a relative score. Treat 'Y' as +1 (benefit of staying open) and 'N' as -1 (cost of staying open). As we iterate, we accumulate this score. The optimal closing time is right after the point where this cumulative score is maximized, meaning we captured the most value from being open.

Algorithm

Initialize res = 0, minPenalty = 0, and penalty = 0.
Iterate through each character at index i:
- Add +1 if the character is 'Y', otherwise add -1.
- If penalty > minPenalty, update minPenalty = penalty and res = i + 1.
Return res.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        res = minPenalty = 0
        penalty = 0

        for i, c in enumerate(customers):
            penalty += 1 if c == 'Y' else -1

            if penalty > minPenalty:
                minPenalty = penalty
                res = i + 1

        return res

public class Solution {
    public int bestClosingTime(String customers) {
        int res = 0, minPenalty = 0, penalty = 0;

        for (int i = 0; i < customers.length(); i++) {
            penalty += customers.charAt(i) == 'Y' ? 1 : -1;

            if (penalty > minPenalty) {
                minPenalty = penalty;
                res = i + 1;
            }
        }

        return res;
    }
}

class Solution {
public:
    int bestClosingTime(string customers) {
        int res = 0, minPenalty = 0, penalty = 0;

        for (int i = 0; i < customers.size(); i++) {
            penalty += customers[i] == 'Y' ? 1 : -1;

            if (penalty > minPenalty) {
                minPenalty = penalty;
                res = i + 1;
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} customers
     * @return {number}
     */
    bestClosingTime(customers) {
        let res = 0,
            minPenalty = 0,
            penalty = 0;

        for (let i = 0; i < customers.length; i++) {
            penalty += customers[i] === 'Y' ? 1 : -1;

            if (penalty > minPenalty) {
                minPenalty = penalty;
                res = i + 1;
            }
        }

        return res;
    }
}

public class Solution {
    public int BestClosingTime(string customers) {
        int res = 0, minPenalty = 0, penalty = 0;

        for (int i = 0; i < customers.Length; i++) {
            penalty += customers[i] == 'Y' ? 1 : -1;

            if (penalty > minPenalty) {
                minPenalty = penalty;
                res = i + 1;
            }
        }

        return res;
    }
}

func bestClosingTime(customers string) int {
    res, minPenalty, penalty := 0, 0, 0

    for i := 0; i < len(customers); i++ {
        if customers[i] == 'Y' {
            penalty++
        } else {
            penalty--
        }

        if penalty > minPenalty {
            minPenalty = penalty
            res = i + 1
        }
    }

    return res
}

class Solution {
    fun bestClosingTime(customers: String): Int {
        var res = 0
        var minPenalty = 0
        var penalty = 0

        for (i in customers.indices) {
            penalty += if (customers[i] == 'Y') 1 else -1

            if (penalty > minPenalty) {
                minPenalty = penalty
                res = i + 1
            }
        }

        return res
    }
}

class Solution {
    func bestClosingTime(_ customers: String) -> Int {
        let chars = Array(customers)
        var res = 0
        var minPenalty = 0
        var penalty = 0

        for i in 0..<chars.count {
            penalty += chars[i] == "Y" ? 1 : -1

            if penalty > minPenalty {
                minPenalty = penalty
                res = i + 1
            }
        }

        return res
    }
}

class Solution {
    /**
     * @param {string} customers
     * @return {number}
     */
    bestClosingTime(customers: string): number {
        let res: number = 0,
            minPenalty: number = 0,
            penalty: number = 0;
        for (let i = 0; i < customers.length; i++) {
            penalty += customers[i] === 'Y' ? 1 : -1;
            if (penalty > minPenalty) {
                minPenalty = penalty;
                res = i + 1;
            }
        }
        return res;
    }
}

impl Solution {
    pub fn best_closing_time(customers: String) -> i32 {
        let s = customers.as_bytes();
        let mut res = 0i32;
        let mut min_penalty = 0i32;
        let mut penalty = 0i32;

        for i in 0..s.len() {
            penalty += if s[i] == b'Y' { 1 } else { -1 };

            if penalty > min_penalty {
                min_penalty = penalty;
                res = i as i32 + 1;
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Confusing Closing Time Semantics

The shop closes at hour i means it is open during hours 0 to i-1 and closed from hour i onward. Many solutions incorrectly interpret this as the shop being open during hour i, leading to off-by-one errors in penalty calculations.

Not Considering Closing at Hour 0 or Hour n

Valid closing times range from 0 (never open) to n (open all day). Forgetting to check i = 0 or i = n causes missing the optimal answer when the best strategy is to never open or stay open the entire day.

Returning Wrong Index on Tie

When multiple closing times have the same minimum penalty, the problem asks for the earliest one. Using <= instead of < when updating the result, or not iterating in the correct order, can return a later hour instead of the earliest optimal hour.