Problem

A search bar at Acme Shop filters a local list of item names as the user types. To avoid recomputing on every keystroke, the search should be debounced: only process a query if no newer query arrives within debounce_ms milliseconds.

Write a function that takes a list of item names, a list of timestamped query updates, and a debounce interval. Return the filtered results for each query that actually executes after debouncing.

Formal Specification

• Input:
  • items: a list of strings
  • events: a list of [timestamp, query] pairs sorted by non-decreasing timestamp
  • debounce_ms: a non-negative integer
• Output:
  • A list of [run_timestamp, filtered_items] pairs, in execution order
• A query matches an item if the query appears as a case-insensitive substring of the item.
• If the query is an empty string, all items match.
• An event executes at timestamp + debounce_ms only if no later event occurs at or before that execution time.

Examples

Example 1 Input: items = ["Apple", "Banana", "Apricot"], events = [[0, "a"], [100, "ap"], [400, "app"]], debounce_ms = 200 Output: [[300, ["Apple", "Apricot"]], [600, ["Apple"]]] Explanation: The query at 0 is canceled by the event at 100. The query "ap" runs at 300, and "app" runs at 600.

Example 2 Input: items = ["Desk", "Chair"], events = [[50, ""]], debounce_ms = 100 Output: [[150, ["Desk", "Chair"]]] Explanation: An empty query returns all items.

Constraints

• 1 <= len(items) <= 10^4
• 0 <= len(events) <= 10^4
• 0 <= debounce_ms <= 10^6
• 0 <= timestamp <= 10^9
• events is sorted by non-decreasing timestamp