Click Stream Funnel Count
A growth team analyses a user's click stream to detect whether they completed a defined funnel: e.g. view → add_to_cart → checkout → pay. The funnel must appear as an ordered subsequence (other clicks may interleave). Count how many distinct users completed the funnel.
Problem
Given a list of events where each event is (user_id, action), and a list of funnel actions in order, return the number of distinct user_ids whose events contain the funnel as an ordered subsequence (other actions may interleave).
Input
Up to 10^5 events. Each event has a user_id string (≤ 16 chars) and an action string (≤ 16 chars). Funnel is a list of 1 ≤ k ≤ 6 action strings.
Output
A single integer — the count of distinct completing users.
Constraints
- Up to 100,000 events, sorted by event timestamp (so traversal order is the event order)
- 1 ≤ funnel length ≤ 6
- Other actions between funnel steps are allowed
- Each funnel action must be matched exactly (no fuzzy match)
Examples
Example 1
Input
events = [(u1, view), (u1, cart), (u2, view), (u1, pay), (u1, checkout)], funnel = [view, cart, checkout, pay]
Output
0
u1 has view, cart, then pay BEFORE checkout. Funnel requires checkout BEFORE pay. So u1 fails. u2 only has view. Count = 0.
Example 2
Input
events = [(u1, view), (u1, cart), (u1, checkout), (u1, pay)], funnel = [view, cart, checkout, pay]
Output
1
u1 hits the funnel in order. Count = 1.