DAY 87 - 2483. Minimum Penalty for a Shop

Hey Guys! Nayan here and we are going to solve another daily leetcode question. I will be taking you guys from intuition to algorithm so stick with me. Incase you don't understand some part , please feel free to ask in comments.

Question: 2483. Minimum Penalty for a Shop

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.

Approach:

The core insight is to closely examine how customers join and leave the line, particularly when the store is nearing closing time. We take advantage of the fact that customers already in line when the store closes can be served, while those arriving later might not have enough time for service.

Maintaining a Counter: The solution maintains a counter, customerLeft, which essentially keeps track of customers in the queue at any given moment.

Optimal Closing Time: As the solution iterates through the list of customers, it reacts to different scenarios:

When a customer arrives ('Y'), it increases the customerLeft counter.
If there are customers in line (customerLeft > 0), it updates the potential optimal closing time (res) with the current time. This captures the idea that customers who are already in line when the store closes can still be served.
If a customer departs ('N'), the customerLeft counter decreases.

Code:

class Solution {
public:
    int bestClosingTime(string customers) {
        int res = 0;
        int customerLeft = 0;

        for (int i = 0; i < customers.length(); i++) {
            if (customers[i] == 'Y') {
                customerLeft++;

                if (customerLeft > 0) {
                    res = i + 1;
                    customerLeft = 0;
                }
            } else {
                customerLeft--;
            }
        }

        return res;        
    }
};

Complexity Analysis: