Transaction Deduplication

Problem Context

You are a backend engineer at a fintech company. Due to network instability, your payment service sometimes receives duplicate transaction requests. Your task is to build a deduplication system that identifies and filters out duplicate transactions before they are processed.

A transaction is represented as a string in the format: "userId:amount:timestamp". Two transactions are considered duplicates if they share the same userId and amount, and their timestamps differ by at most k seconds.

Given a list of transaction strings and an integer k, return a list of unique transaction IDs (0-indexed positions) that should be processed. If a transaction is a duplicate of a previously accepted transaction, it should be rejected. Transactions should be evaluated in the order they appear.

Input/Output Format

Input:

• transactions: A list of strings, each in the format "userId:amount:timestamp" where userId is alphanumeric, amount is a positive integer (in cents), and timestamp is a non-negative integer (Unix seconds).
• k: An integer representing the deduplication window in seconds (inclusive).

Output:

• A list of integers representing the 0-indexed positions of transactions that should be accepted (not duplicates).

Examples

Example 1

Input: transactions = ["user1:500:1000", "user2:300:1001", "user1:500:1005", "user1:500:1012"], k = 10

Output: [0, 1, 3]

Explanation:

• Transaction 0 (user1:500:1000): No prior transaction — accepted.
• Transaction 1 (user2:300:1001): Different user — accepted.
• Transaction 2 (user1:500:1005): Same user+amount as transaction 0. |1005 - 1000| = 5 <= 10 — duplicate, rejected.
• Transaction 3 (user1:500:1012): Same user+amount. |1012 - 1000| = 12 > 10 — accepted (outside window).

Example 2

Input: transactions = ["alice:200:0", "alice:200:5", "alice:200:10"], k = 5

Output: [0, 2]

Explanation:

• Transaction 0: Accepted. Window anchor is 0.
• Transaction 1: — duplicate, rejected.