Minimum Penalty for a Shop - Practice Coding Problems

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 i^th character is 'Y', it means that customers come at the i^th hour
If the i^th character is 'N', it means that no customers come at the i^th hour

If the shop closes at the j^th 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: If a shop closes at the j^th hour, it means the shop is closed at the hour j.

Input & Output

Example 1 — Basic Case

$ Input: customers = "YYNY"

› Output: 2

💡 Note: Closing at hour 2 gives penalty of 1: open during hours 0,1 (both Y, no penalty) and closed during hours 2,3 (one Y at hour 3, penalty=1)

Example 2 — All Customers

$ Input: customers = "YYYY"

› Output: 4

💡 Note: Best to stay open all hours (close at hour 4): no penalty for being open with customers, penalty=0

Example 3 — No Customers

$ Input: customers = "NNNN"

› Output: 0

💡 Note: Best to close immediately (hour 0): no penalty for being closed when no customers come, penalty=0

Constraints

1 ≤ customers.length ≤ 10⁵
customers consists only of characters 'Y' and 'N'

Visualization

Tap to expand

Understanding the Visualization

Input

Customer log string with Y (customer) and N (no customer)

Process

Calculate penalty for each closing hour

Output

Earliest hour with minimum penalty

Key Takeaway

🎯 Key Insight: Penalty changes predictably as closing hour moves right: lose N penalties, gain Y penalties

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is that as we move the closing hour from left to right, the penalty changes predictably: -1 for each 'Y' we include in open hours, +1 for each 'N'. The optimal approach uses this to calculate penalties in O(n) time by starting with all hours closed and incrementally opening each hour. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n)	O(1)	Pre-calculate penalty changes to avoid recalculating from scratch each time
Brute Force	O(n²)	O(1)	Calculate penalty for each possible closing hour from 0 to n

Prefix Sum Optimization — Algorithm Steps

Step 1: Calculate penalty for closing at hour 0 (all hours closed)
Step 2: For each hour, update penalty based on opening that hour
Step 3: Track minimum penalty and earliest hour achieving it

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Closed

Begin with penalty for closing at hour 0

Open Hours

For each hour opened, adjust penalty incrementally

Track Minimum

Keep track of minimum penalty and best hour

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* customers) {
    int n = strlen(customers);
    
    // Calculate penalty for closing at hour 0 (all hours closed)
    int penalty = 0;
    for (int i = 0; i < n; i++) {
        if (customers[i] == 'Y') penalty++;
    }
    
    int minPenalty = penalty;
    int bestHour = 0;
    
    // Try opening each hour one by one
    for (int i = 0; i < n; i++) {
        // Opening hour i: remove Y penalty if Y, add N penalty if N
        if (customers[i] == 'Y') {
            penalty--; // No longer penalized for this Y
        } else {
            penalty++; // Now penalized for this N
        }
        
        // Check if this is better
        if (penalty < minPenalty) {
            minPenalty = penalty;
            bestHour = i + 1;
        }
    }
    
    return bestHour;
}

int main() {
    char customers[100001];
    fgets(customers, sizeof(customers), stdin);
    customers[strcspn(customers, "\n")] = 0;
    
    int result = solution(customers);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string to calculate initial penalty, then single pass to update incrementally

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for penalty tracking and counters

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler