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:
+1for every hour the shop is open and no customer comes ('N'), and+1for 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^5customers consists only of the characters 'Y' and 'N'
Hints for Minimum Penalty for a Shop
Hint 1
Computing every closing hour's penalty from scratch is O(n²).
Hint 2
Moving the closing hour from
jtoj + 1only changes how hourjis charged.Hint 3
Start with the penalty of closing at 0 (the number of
Ys) and sweep: aYat hourjlowers the penalty by one, anNraises 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
- Closing at hour 0 costs the number of
'Y'characters; setpenaltyto that,best = penaltyandanswer = 0. - For each hour
jfrom 0 ton - 1: ifcustomers[j] == 'Y', decreasepenalty(that customer is now served); otherwise increase it (the shop now idles that hour). - If
penalty < best, recordbest = penaltyandanswer = j + 1. - 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 considerj + 1up ton. - 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 answerJava
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