Minimum Penalty for a Shop

PROBLEM

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.

Example1

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

Example2

*Input*: customers = "NNNNN"
*Output*: 0
*Explanation*: It is best to close the shop at the 0th hour as no customers arrive.

Example3

*Input*: customers = "YYYY"
*Output*: 4
*Explanation*: It is best to close the shop at the 4th hour as customers arrive at each hour.

SOLVING

We’ll get the value for the 0th hour and for each hour we base on the previous value to obtain the value for this hour

Steps

• Create variable bestHour, minimumPenalties and current initialize at 0
• First get the value for the 0th hour. So iterate on the string and for each 'Y' and increases minimumPenalties by 1
• current take the value of minimumPenalties
• For each hour (string’s size) from 1th because we already compute 0th:
  • Increase current if the last hour was a 'Y' otherwise decrease by 1
  • If current is strictly lower than minimumPenalties, update minimumPenalties by current and bestHour by the index of the loop
• Return BestHour

Code

class Solution {
public:
  int bestClosingTime(string customers) {
    int minimumPenalties = 0, bestHour = 0, current = 0;
    int size = customers.size();

    // Getting the value if close at 0th so to each hour with customers 'Y' penalty increases by 1
    for (int i = 0; i < size; i++)
      if (customers[i] == 'Y')
	minimumPenalties++;

    // For each hour change the value looking the last hour and update the bestHour and the minimumPenalties accordingly
    current = minimumPenalties;
    for (int i = 1; i <= size; i++) {
      current += (customers[i - 1] == 'Y') ? -1 : 1;
      if (current < minimumPenalties) {
	bestHour = i;
	minimumPenalties = current;
      }
    }
    return bestHour;
  }
};

• PROBLEM