You are given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters 'N' and 'Y':
ith character is 'Y', it means that customers come at the ith hour'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:
1.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 <= 105customers consists only of characters 'Y' and 'N'.This approach involves preprocessing the input string to obtain counts of 'Y' before each hour and 'N' from each hour to the end. This allows us to quickly calculate the penalty for closing the shop at any given hour.
The implementation uses prefix and suffix arrays to keep track of Y and N counts up to each hour. This preprocessing helps calculate the penalty efficiently for each potential closing time point.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n)
The sliding window approach attempts to keep a running window of penalty calculation as the considered closing hour is incremented, using just a few shared variables instead of arrays.
This implementation uses two counters: 'open_no_customers' for open hours without customers and 'closed_with_customers' for closed hours with customers. As we evaluate each closing hour, penalties are adjusted efficiently without needing full array storage.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Cumulative Sum Approach | Time Complexity: O(n) |
| Sliding Window Approach | Time Complexity: O(n) |
Minimum Penalty for a Shop - Leetcode 2483 - Python • NeetCodeIO • 10,316 views views
Watch 9 more video solutions →Practice Minimum Penalty for a Shop with our built-in code editor and test cases.
Practice on FleetCode