Most Common Three-Website Visit Sequence Across Users

You are given a log of website visits. Record `i` says that the user `usernames[i]` visited the website `websites[i]` at time `timestamps[i]`. The three lists have the same length, and the records are not sorted in any particular order. A **pattern** is an ordered list of exactly three website names. The names do not have to be different: `["home", "home", "cart"]` is a valid pattern. A user **follows** a pattern if, once that user's visits are arranged in increasing timestamp order, the three websites of the pattern appear in that order within the user's sequence, not necessarily next to each other. The **score** of a pattern is the number of distinct users who follow it. Return the pattern with the highest score. ### Function Signature ```python def most_common_visit_pattern(usernames: list[str], timestamps: list[int], websites: list[str]) -> list[str]: ``` ### Rules - A user adds at most 1 to a pattern's score, no matter how many different ways the user's visit sequence contains that pattern. - Only visits by the same user combine into a pattern; visits by different users never combine. - Ties: if several patterns share the highest score, return the lexicographically smallest one. Compare the first website names; if they are equal, compare the second; if those are equal, compare the third. Names are compared as ordinary strings of lowercase letters, so `"ab"` comes before `"b"` and `"cart"` comes before `"carts"`. - Return the pattern as a list of three strings. ### Constraints - `3 <= n <= 100`, where `n = len(usernames) = len(timestamps) = len(websites)` - `1 <= len(usernames[i]) <= 10` and `1 <= len(websites[i]) <= 10`; both consist of lowercase English letters only. - `1 <= timestamps[i] <= 10^9` - All timestamps that belong to the same user are distinct, so every user's visits have one unambiguous order. Different users may share timestamps. - At least one user has three or more visits, so at least one pattern has a score of at least 1. ### Examples **Example 1** ```text Input: usernames = ["ana", "ana", "ana", "ben", "ben", "ben", "ben", "cy", "cy", "cy"] timestamps = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] websites = ["home", "search", "cart", "home", "search", "deals", "cart", "search", "home", "cart"] Output: ["home", "search", "cart"] ``` In time order, ana visits home, search, cart; ben visits home, search, deals, cart; cy visits search, home, cart. Both ana and ben follow `["home", "search", "cart"]` (ben's "deals" visit is simply skipped), giving it score 2. Every other pattern has score 1. **Example 2** ```text Input: usernames = ["dee", "eli", "dee", "eli", "dee", "eli"] timestamps = [30, 5, 10, 7, 20, 6] websites = ["blog", "shop", "blog", "shop", "news", "about"] Output: ["blog", "news", "blog"] ``` Sorted by time, dee visits blog (10), news (20), blog (30), and eli visits shop (5), about (6), shop (7). Each user follows exactly one pattern, so both patterns have score 1, and `["blog", "news", "blog"]` is lexicographically smaller. **Example 3** ```text Input: usernames = ["fay", "fay", "fay", "fay", "gus", "gus", "gus"] timestamps = [1, 2, 3, 4, 1, 2, 3] websites = ["a", "b", "b", "b", "b", "b", "b"] Output: ["b", "b", "b"] ``` fay's sequence is a, b, b, b. It contains `["a", "b", "b"]` in three different ways, but fay still adds only 1 to that pattern's score; fay also follows `["b", "b", "b"]`. gus's sequence b, b, b follows only `["b", "b", "b"]`. So `["b", "b", "b"]` scores 2 and `["a", "b", "b"]` scores 1.