Leetcode # 2483. Minimum Penalty for a Shop

Problem

https://leetcode.com/problems/minimum-penalty-for-a-shop

Solution

Time Complexity: O(len(customers))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def bestClosingTime(self, customers: str) -> int:
    close_at = 0
    penalty = min_penalty = customers.count("Y")
    for j in range(1, len(customers) + 1):
      penalty += -1 if customers[j - 1] == "Y" else 1
      if penalty < min_penalty:
        close_at = j
        min_penalty = penalty
    return close_at

Two Passes → One Pass

因為題目沒有要求正確的 minimum penalty 的值
求的是相對關係下「令 penalty 最小」的「最早的關門時間」
所以不去計算起始的 penalty 也沒關係

penalty = min_penalty = customers.count(“Y”)0

Last Updated on 2023/08/29 by A1go