Skip to content

2483. Minimum Penalty for a Shop

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

Solutions

Solution 1: Enumeration

If the shop closes at hour \(0\), then the cost is the number of character 'Y' in \(\textit{customers}\). We initialize the answer variable \(\textit{ans}\) to \(0\), and the cost variable \(\textit{cost}\) to the number of character 'Y' in \(\textit{customers}\).

Next, we enumerate the shop closing at hour \(j\) (\(1 \leq j \leq n\)). If \(\textit{customers}[j - 1]\) is 'N', it means no customer arrived during the open period, and the cost increases by \(1\); otherwise, it means a customer arrived during the closed period, and the cost decreases by \(1\). If the current cost \(\textit{cost}\) is less than the minimum cost \(\textit{mn}\), we update the answer variable \(\textit{ans}\) to \(j\), and update the minimum cost \(\textit{mn}\) to the current cost \(\textit{cost}\).

After the traversal ends, we return the answer variable \(\textit{ans}\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(\textit{customers}\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def bestClosingTime(self, customers: str) -> int:
        ans = 0
        mn = cost = customers.count("Y")
        for j, c in enumerate(customers, 1):
            cost += 1 if c == "N" else -1
            if cost < mn:
                ans, mn = j, cost
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        int ans = 0, cost = 0;
        for (int i = 0; i < n; i++) {
            if (customers.charAt(i) == 'Y') {
                cost++;
            }
        }
        int mn = cost;
        for (int j = 1; j <= n; j++) {
            cost += customers.charAt(j - 1) == 'N' ? 1 : -1;
            if (cost < mn) {
                ans = j;
                mn = cost;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int bestClosingTime(string customers) {
        int ans = 0;
        int cost = 0;
        for (char c : customers) {
            if (c == 'Y') {
                cost++;
            }
        }
        int mn = cost;
        for (int j = 1; j <= customers.size(); ++j) {
            cost += customers[j - 1] == 'N' ? 1 : -1;
            if (cost < mn) {
                ans = j;
                mn = cost;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func bestClosingTime(customers string) int {
    ans := 0
    cost := strings.Count(customers, "Y")
    mn := cost
    for j := 1; j <= len(customers); j++ {
        c := customers[j-1]
        if c == 'N' {
            cost++
        } else {
            cost--
        }
        if cost < mn {
            ans = j
            mn = cost
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function bestClosingTime(customers: string): number {
    let ans = 0;
    let cost = 0;
    for (const ch of customers) {
        if (ch === 'Y') {
            cost++;
        }
    }
    let mn = cost;

    for (let j = 1; j <= customers.length; j++) {
        const c = customers[j - 1];
        cost += c === 'N' ? 1 : -1;
        if (cost < mn) {
            mn = cost;
            ans = j;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn best_closing_time(customers: String) -> i32 {
        let bytes = customers.as_bytes();

        let mut cost: i32 = bytes.iter().filter(|&&c| c == b'Y').count() as i32;
        let mut mn = cost;
        let mut ans: i32 = 0;

        for j in 1..=bytes.len() {
            let c = bytes[j - 1];
            if c == b'N' {
                cost += 1;
            } else {
                cost -= 1;
            }
            if cost < mn {
                mn = cost;
                ans = j as i32;
            }
        }
        ans
    }
}

Comments