LeetCode 2483. Minimum Penalty for a Shop Solution in Java, C++, Python & More | Explanation + Code

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 customers. We initialize the answer variable ans to 0, and the cost variable cost to the number of character 'Y' in customers.

Next, we enumerate the shop closing at hour j (1 ≤ j ≤ n). If 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 cost is less than the minimum cost mn, we update the answer variable ans to j, and update the minimum cost mn to the current cost cost.

After the traversal ends, we return the answer variable ans.

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

PythonJavaC++GoTypeScriptRustC#

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

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 } }(code-box)

public 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[i] == 'Y') { cost++; } } int mn = cost; for (int j = 1; j <= n; j++) { cost += customers[j - 1] == 'N' ? 1 : -1; if (cost < mn) { ans = j; mn = cost; } } return ans; } }(code-box)