Minimum Penalty for a Shop

Medium
1242.

Minimum Penalty for a Shop

Minimum Penalty for a Shop is a medium coding problem on strings and prefix sum, asked in Amazon, Google and Microsoft interviews.

A shop's log for one day is a string customers of 'Y' and 'N': customers[i] == 'Y' means some customer arrived during hour i, 'N' means nobody did.

If the shop closes at hour j (where 0 <= j <= n), it is open for hours 0..j-1 and closed for hours j..n-1. The penalty is:

  • +1 for every hour the shop is open and no customer comes ('N'), and
  • +1 for every hour the shop is closed and a customer comes ('Y').

Return the earliest hour at which the shop should close to get the minimum penalty.

Example 1

Input
customers = "NYYN"
Output
3
Explanation
Closing at 3 costs 1 (the open `N` at hour 0). Every other hour costs at least 2.

Example 2

Input
customers = "NNNN"
Output
0
Explanation
Closing immediately costs nothing.

Example 3

Input
customers = "YYYY"
Output
4
Explanation
Stay open all day.

Constraints

  • 1 <= customers.length <= 10^5
  • customers consists only of the characters 'Y' and 'N'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} customers
 * @return {number}
 */
var bestClosingTime = function(customers) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Penalty for a Shop — Solution in Python, Java & C++

Minimum Penalty for a Shop solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Penalty for a Shop is a medium coding problem on strings and prefix sum, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings, Prefix Sum
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A shop's log for one day is a string customers of 'Y' and 'N': customers[i] == 'Y' means some customer arrived during hour i, 'N' means nobody did.

If the shop closes at hour j (where 0 <= j <= n), it is open for hours 0..j-1 and closed for hours j..n-1. The penalty is:

  • +1 for every hour the shop is open and no customer comes ('N'), and
  • +1 for every hour the shop is closed and a customer comes ('Y').

Return the earliest hour at which the shop should close to get the minimum penalty.

Example 1

Input: customers = "NYYN"
Output: 3
Explanation: Closing at 3 costs 1 (the open `N` at hour 0). Every other hour costs at least 2.

Example 2

Input: customers = "NNNN"
Output: 0
Explanation: Closing immediately costs nothing.

Example 3

Input: customers = "YYYY"
Output: 4
Explanation: Stay open all day.

Constraints

  • 1 <= customers.length <= 10^5
  • customers consists only of the characters 'Y' and 'N'

Hints for Minimum Penalty for a Shop

  1. Hint 1

    Computing every closing hour's penalty from scratch is O(n²).

  2. Hint 2

    Moving the closing hour from j to j + 1 only changes how hour j is charged.

  3. Hint 3

    Start with the penalty of closing at 0 (the number of Ys) and sweep: a Y at hour j lowers the penalty by one, an N raises it by one. Keep the first hour reaching the minimum.

How to solve Minimum Penalty for a Shop

Sweep the closing hour from 0 to n. Each step only re-charges a single hour, so the penalty changes by exactly one.

Approach

  1. Closing at hour 0 costs the number of 'Y' characters; set penalty to that, best = penalty and answer = 0.
  2. For each hour j from 0 to n - 1: if customers[j] == 'Y', decrease penalty (that customer is now served); otherwise increase it (the shop now idles that hour).
  3. If penalty < best, record best = penalty and answer = j + 1.
  4. Return answer.

Why it works

Closing at j + 1 instead of j moves hour j from the closed part to the open part; nothing else changes. A 'Y' hour stops costing 1 and an 'N' hour starts costing 1. Tracking the running penalty therefore gives every closing hour's cost, and updating only on a strictly smaller value keeps the earliest optimal hour.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The answer can be n (stay open the whole day), so the sweep must consider j + 1 up to n.
  • Use a strict < so ties keep the earliest hour.
  • Do not confuse the two charges: idle open hours are 'N', missed customers are 'Y'.

Reference solution

Python

def bestClosingTime(customers: str) -> int:
    penalty = customers.count("Y")
    best = penalty
    answer = 0
    for j, ch in enumerate(customers):
        penalty += -1 if ch == "Y" else 1
        if penalty < best:
            best = penalty
            answer = j + 1
    return answer

Java

public static int bestClosingTime(String customers) {
    int n = customers.length(), penalty = 0;
    for (int i = 0; i < n; i++) if (customers.charAt(i) == 'Y') penalty++;
    int best = penalty, answer = 0;
    for (int j = 0; j < n; j++) {
        penalty += customers.charAt(j) == 'Y' ? -1 : 1;
        if (penalty < best) { best = penalty; answer = j + 1; }
    }
    return answer;
}

C++

int bestClosingTime(string customers) {
    int n = customers.size(), penalty = 0;
    for (char ch : customers) if (ch == 'Y') penalty++;
    int best = penalty, answer = 0;
    for (int j = 0; j < n; j++) {
        penalty += customers[j] == 'Y' ? -1 : 1;
        if (penalty < best) { best = penalty; answer = j + 1; }
    }
    return answer;
}

JavaScript

var bestClosingTime = function(customers) {
    var penalty = 0;
    for (var i = 0; i < customers.length; i++) if (customers[i] === "Y") penalty++;
    var best = penalty, answer = 0;
    for (var j = 0; j < customers.length; j++) {
        penalty += customers[j] === "Y" ? -1 : 1;
        if (penalty < best) { best = penalty; answer = j + 1; }
    }
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Prefix Sum