Problem Statement in English

You’re given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters 'N' and 'Y':

  • 'Y' indicates that customers come to the shop at the ith hour
  • 'N' indicates that no customers come to the shop at the ith

Your task is to find the best closing time to minimize the penalty. 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.

Approach

We can use a prefix sum to efficiently keep track of penalties incurred when the shop is open during hours with no customers, and a suffix sum to track penalties incurred when the shop is closed during hours with customers.

We can then use these two arrays to calculate the total penalty for closing the shop at each hour and find the hour that results in the minimum penalty.

Solution in Python


class Solution:
    def bestClosingTime(self, customers: str) -> int:
        customers += "N"
        L = len(customers)
        # no customer but shop open penalty (prefix sum)
        prefix = [0] * L
        # customer comes but shop closed penalty (suffix sum)
        suffix = [0] * L

        ri, rv = 0, inf

        for i in range(1, L):
            # prefix
            prefix[i] = prefix[i - 1] + int(customers[i - 1] == "N")

        suffix[-1] = int(customers[-1] == "Y")
        for i in reversed(range(L - 1)):
            # suffix
            suffix[i] = suffix[i + 1] + int(customers[i] == "Y")

        # closing it on the ith day -> prefix[i] + suffix[i]
        for i in range(L):
            v = prefix[i] + suffix[i]

            if v < rv:
                rv = v
                ri = i

        return ri

Complexity

  • Time: $O(n)$
    Since we traverse the customers string a constant number of times, the time complexity is linear with respect to the length of the string.

  • Space: $O()$
    We use two additional arrays of size n to store the prefix and suffix penalties, resulting in linear space complexity.

And we are done.