Per-Key Fixed-Window Cost Limiter with ALLOW and RESET Commands

You are building a rate limiter that meters cost instead of counting requests. Every key (for example a user or an API client) may spend at most limit cost units in each fixed time window of window seconds. Windows are aligned to multiples of window: the window that contains timestamp t starts at floor(t / window) * window and ends just before floor(t / window) * window + window.

Process a list of commands in order and return one output string per command. There are two kinds of command:

• ALLOW key cost timestamp: let usage be the total cost already accepted for key in the window that contains timestamp. If usage + cost <= limit, accept the request, add cost to that usage, and output "true". Otherwise output "false" and record nothing.
• RESET key timestamp: clear all usage recorded for key and output "ok".

Function Signature

def process_commands(limit: int, window: int, commands: list[str]) -> list[str]:

Rules

• Keys are independent: one key's usage never affects another key.
• Usage accepted in one window never counts toward a later window. The first ALLOW for a key in a new window starts from zero usage.
• A rejected ALLOW changes nothing, so a later, cheaper request in the same window can still be accepted.
• A request whose cost alone is greater than limit is always rejected.
• RESET may name a key that has never been seen; it still outputs "ok". After a RESET, the key's usage in the current window is zero.
• Outputs are the exact lowercase strings "true", "false" and "ok", one per command, in command order.

Constraints

• 1 <= len(commands) <= 200000
• 1 <= limit <= 10^9 and 1 <= window <= 10^9
• Every command is either "ALLOW key cost timestamp" or "RESET key timestamp", with tokens separated by single spaces. key is a non-empty string of at most 20 lowercase letters and digits. cost and timestamp are decimal integers with no sign and no leading zeros (except the number 0 itself).
• 1 <= cost <= 10^9
• 0 <= timestamp <= 10^15. Timestamps and window starts can exceed 2^31 - 1, so use 64-bit integers for them.
• Timestamps are non-decreasing across the whole list: every command's timestamp is greater than or equal to the previous command's timestamp.
• The returned list has exactly len(commands) elements and is uniquely determined by the input.

Examples

Example 1

• Input: limit = 10, window = 60, commands = ["ALLOW alice 3 0", "ALLOW alice 8 10", "ALLOW alice 7 61", "RESET alice 62", "ALLOW alice 10 63", "ALLOW alice 1 64"]
• Output: ["true", "false", "true", "ok", "true", "false"]
• Explanation: Timestamps 0 and 10 fall in the window starting at 0. The cost 3 is accepted (usage 3), and then 3 + 8 = 11 > 10, so the cost 8 is rejected. Timestamp 61 falls in the window starting at 60, where usage starts at zero, so the cost 7 is accepted. RESET clears alice's usage, so the cost 10 is accepted (usage 10), and the final cost 1 is rejected because 10 + 1 > 10.

Example 2

• Input: limit = 5, window = 10, commands = ["ALLOW a 5 9", "ALLOW b 2 9", "ALLOW a 1 9", "ALLOW a 1 10", "ALLOW b 4 19", "ALLOW b 3 19", "ALLOW b 1 19", "RESET c 20", "ALLOW c 5 20"]
• Output: ["true", "true", "false", "true", "true", "false", "true", "ok", "true"]
• Explanation: At timestamp 9 (window starting at 0), a spends its whole budget and its next request is rejected, while b is unaffected. Timestamp 10 starts a new window, so a is accepted again. At timestamp 19 (window starting at 10), b starts from zero: the cost 4 is accepted, 4 + 3 > 5 is rejected and records nothing, so 4 + 1 = 5 is still accepted. RESET on the unseen key c outputs "ok", and c can then spend its full budget.

Example 3

• Input: limit = 999999999, window = 1000000000, commands = ["ALLOW k 1000000000 999999999999999", "ALLOW k 999999999 999999999999999", "ALLOW k 1 999999999999999", "ALLOW k 1 1000000000000000"]
• Output: ["false", "true", "false", "true"]
• Explanation: The first cost is larger than limit, so it is rejected. Timestamp 999999999999999 lies in the window starting at 999999000000000, where 999999999 fits exactly and the extra 1 does not. Timestamp 1000000000000000 starts a new window at 1000000000000000, so the cost 1 is accepted.

Cost-Metered Fixed-Window Rate Limiter

Hints

1. Only the current window matters for each key. You never need usage from an earlier window, so you do not need a history of requests.
2. Store two numbers per key: the start of the window its usage belongs to, and that usage. When a request maps to a different window start, treat the stored usage as zero.
3. Check the integer widths before you code: timestamps and window starts go up to 10^15, far beyond 32-bit range.

Approach

Only one window matters for any key at any moment: the window containing the request's timestamp. Timestamps never decrease, so once a key's requests move into a later window, the usage from the earlier window can never count again. That means you need no request history, only a small record per key.

The reference keeps a hash map from each key to a pair (window_start, usage), meaning "this key has accepted usage cost units in the window that starts at window_start".

For ALLOW key cost timestamp, compute start = floor(timestamp / window) * window. If the stored pair exists and its window_start equals start, the current usage is the stored usage. Otherwise (a new key, or usage left over from an older window) the current usage is 0. If usage + cost <= limit, store (start, usage + cost) and output "true". Otherwise output "false" and leave the map untouched. Leaving it untouched is safe even when the stored pair belongs to an older window, because the next ALLOW repeats the same window comparison.

For RESET key timestamp, delete the key from the map and output "ok". A missing entry already means zero usage, so deleting a key that was never seen is harmless.

Integer widths matter in typed languages. Timestamps and window starts reach 10^15, far beyond 32-bit range, so they must be 64-bit integers (long in Java, long long in C++); parsing a timestamp into a 32-bit int either throws or wraps and puts the request in the wrong window. usage + cost is at most 2 * 10^9, which still fits a signed 32-bit int, but the reference keeps it 64-bit too so that no mixed-width arithmetic is needed. In JavaScript every value stays below 2^53, so plain numbers are exact, and timestamp - timestamp % window gives the window start without floating-point division.

Each command costs one split of a short string and one hash-map operation, so the whole run is linear in the number of commands.

• Time complexity: O(n) for n = len(commands): each command has at most about 50 characters, so parsing it and one hash-map lookup take constant time
• Space complexity: O(k) for the per-key state, where k <= n is the number of distinct keys, plus O(n) for the output list