Minimum Penalty for a Shop | Prefix Sum | Single Parse | Leetcode 2483

//2 Pass: Exact Penalty Solution
class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size();

        int closed_penalty = 0;
        for(int i=0;i<n;++i)
            if(customers[i]=='Y')
                closed_penalty++;
    
        int closing_hour = 0;
        int min_penalty = closed_penalty;
        int open_penalty = 0;

        for(int i=0;i<n;++i){
            if(customers[i]=='Y')   closed_penalty--;
            else                    open_penalty++;

            if(min_penalty > closed_penalty + open_penalty){
                min_penalty = closed_penalty + open_penalty;
                closing_hour = i+1;
            }
        }
        return closing_hour;
    }
};

//1 Pass: Relative Penalty Solution
class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size();

        int closed_penalty = 0;
    
        int closing_hour = 0;
        int min_penalty = closed_penalty;
        int open_penalty = 0;

        for(int i=0;i<n;++i){
            if(customers[i]=='Y')   closed_penalty--;
            else                    open_penalty++;

            if(min_penalty > closed_penalty + open_penalty){
                min_penalty = closed_penalty + open_penalty;
                closing_hour = i+1;
            }
        }
        return closing_hour;
    }
};

/*
//JAVA (2-Pass): Exact Penalty Solution
class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();

        // Penalty if shop is closed all day
        int closedPenalty = 0;
        for (int i = 0; i < n; i++) {
            if (customers.charAt(i) == 'Y') {
                closedPenalty++;
            }
        }

        int openPenalty = 0;
        int minPenalty = closedPenalty;
        int closingHour = 0;

        for (int i = 0; i < n; i++) {
            if (customers.charAt(i) == 'Y') {
                closedPenalty--;
            } else {
                openPenalty++;
            }

            if (closedPenalty + openPenalty < minPenalty) {
                minPenalty = closedPenalty + openPenalty;
                closingHour = i + 1;
            }
        }

        return closingHour;
    }
}

// JAVA (1-Pass): Relative Penalty Solution
class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();

        int curPenalty = 0;   // relative penalty
        int minPenalty = 0;
        int closingHour = 0;

        for (int i = 0; i < n; i++) {
            if (customers.charAt(i) == 'Y') {
                curPenalty--;   // removing future Y penalty
            } else {
                curPenalty++;   // adding open N penalty
            }

            if (curPenalty < minPenalty) {
                minPenalty = curPenalty;
                closingHour = i + 1;
            }
        }

        return closingHour;
    }
}

#Python (2-Pass): Exact Penalty Solution
class Solution:
    def bestClosingTime(self, customers: str) -> int:
        n = len(customers)

        # Penalty if shop is closed all day
        closed_penalty = customers.count('Y')

        open_penalty = 0
        min_penalty = closed_penalty
        closing_hour = 0

        for i in range(n):
            if customers[i] == 'Y':
                closed_penalty -= 1
            else:
                open_penalty += 1

            if closed_penalty + open_penalty < min_penalty:
                min_penalty = closed_penalty + open_penalty
                closing_hour = i + 1

        return closing_hour


#Python (1-Pass): Relative Penalty SOlution
class Solution:
    def bestClosingTime(self, customers: str) -> int:
        cur_penalty = 0   # relative penalty
        min_penalty = 0
        closing_hour = 0

        for i, ch in enumerate(customers):
            if ch == 'Y':
                cur_penalty -= 1
            else:
                cur_penalty += 1

            if cur_penalty < min_penalty:
                min_penalty = cur_penalty
                closing_hour = i + 1

        return closing_hour
*/