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.
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.
Input: customers = "NNNNN"
Output: 0
Explanation: It is best to close the shop at the 0th hour as no customers arrive.
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'.
Contents
- Solution 1 - Create prefix sum array scanning through N's and postfix sum array scanning Y's
- Solution 2 - Using prefix sum, memory optimized approach
In this approach, we will compute a prefix sum, by looking at 'N's, so we will be pre-computing what
would be the penalty if there were no customers at jth hour, meaning that we will be looking at how many N's we have seen until now but the shop is opened.
When we compute prefix it's going to be exclusive.
We will also compute a postfix sum, by looking at 'Y's, so we will be pre-computing what would be the penalty
if the shop is closed at jth hour, meaning that we will be looking at Y's from backwards.
When we compute postfix it's going to be inclusive.
The reason why we chose for exclusive when calculating prefix sum, and inclusive when calculating postfix sum is because, when we look at these two arrays
to get the penalty at jth hour, we would be able calculate penalty looking at prefix array that could incurred by N's on left, if current element in Y in postfix array, or vice versa.
public class MinimumPenaltyForAShop {
static int bestClosingTime(String customers) {
int n = customers.length();
int[] prefix = new int[n+1];
int[] postfix = new int[n+1];
// customers = "YYNY" , prefix[0] = 0 since there will not be any N's before this
for(int i=1; i<prefix.length; i++) {
prefix[i] = prefix[i-1];
if(customers.charAt(i-1) == 'N') {
prefix[i] += 1;
}
}
//postfix[n] = 0 since there will not be any Y's after this
// in postfix, we are counting Y's until now + current one
for(int i=postfix.length-2; i>=0; i--) {
postfix[i] = postfix[i+1];
if(customers.charAt(i) == 'Y') {
postfix[i] += 1;
}
}
int minPenalty = Integer.MAX_VALUE;
int index = 0;
for(int i=0;i<prefix.length; i++) {
int penalty = prefix[i] + postfix[i];
if(penalty < minPenalty) {
minPenalty = penalty;
index = i;
}
}
return index;
}
public static void main(String[] args) {
System.out.println(bestClosingTime("YYNY"));
System.out.println(bestClosingTime("NNNNN"));
System.out.println(bestClosingTime("YYYY"));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the length of customers string.
Space complexity: O(n), since we are creating prefix and postfix sum arrays with size n.
In this approach, we will first compute the maximum penalty possible, that is what if the shop is closed at 0th hour, loop through input string customers
and count all Y's, store it in a variable penalty.
Next, we will loop through customers string one more time, and try to minimize the penalty, that is if the element is 'Y', that means
we can definitely keep the shop open and decrease the penalty by 1, but if we see the element as 'N',
that means if the shop is opened and no customers showed up, so increment the penalty. While incrementing or decrementing penalty
keep track of minimum penalty so far that can be achieved and track the index where minimum penalty is found. Finally return index +1 as answer, this is because
we will closing the shop after minimum penalty is achieved.
public class MinimumPenaltyForAShop {
static int bestClosingTimeMemoryOptimized(String customers) {
int penalty = 0;
int n = customers.length();
for(int i=0; i<n; i++) {
if(customers.charAt(i) == 'Y') {
penalty++;
}
}
int minPenalty = penalty;
int index = 0;
for(int i=0; i<n; i++) {
if(customers.charAt(i) == 'Y') {
penalty--;
} else {
penalty++;
}
if(penalty < minPenalty) {
minPenalty = penalty;
index = i+1;
}
}
return index;
}
public static void main(String[] args) {
System.out.println("############### Memory optimized ######################");
System.out.println(bestClosingTimeMemoryOptimized("YYNY"));
System.out.println(bestClosingTimeMemoryOptimized("NNNNN"));
System.out.println(bestClosingTimeMemoryOptimized("YYYY"));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the length of customers string.
Space complexity: O(1).
Above implementations source code can be found at
GitHub link for Java code