1152. Analyze User Website Visit Pattern

You are given two string arrays username and website and an integer array timestamp. All the given arrays are of the same length and the tuple [username[i], website[i], timestamp[i]] indicates that the user username[i] visited the website website[i] at time timestamp[i].

A pattern is a list of three websites (not necessarily distinct).

• For example, ["home", "away", "love"], ["leetcode", "love", "leetcode"], and ["luffy", "luffy", "luffy"] are all patterns.

The score of a pattern is the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.

• For example, if the pattern is ["home", "away", "love"], the score is the number of users x such that x visited "home" then visited "away" and visited "love" after that.
• Similarly, if the pattern is ["leetcode", "love", "leetcode"], the score is the number of users x such that x visited "leetcode" then visited "love" and visited "leetcode" one more time after that.
• Also, if the pattern is ["luffy", "luffy", "luffy"], the score is the number of users x such that x visited "luffy" three different times at different timestamps.

Return the pattern with the largest score. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.

Example 1:

Input: username = ["joe","joe","joe","james","james","james","james","mary","mary","mary"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = ["home","about","career","home","cart","maps","home","home","about","career"]
Output: ["home","about","career"]
Explanation: The tuples in this example are:
["joe","home",1],["joe","about",2],["joe","career",3],["james","home",4],["james","cart",5],["james","maps",6],["james","home",7],["mary","home",8],["mary","about",9], and ["mary","career",10].
The pattern ("home", "about", "career") has score 2 (joe and mary).
The pattern ("home", "cart", "maps") has score 1 (james).
The pattern ("home", "cart", "home") has score 1 (james).
The pattern ("home", "maps", "home") has score 1 (james).
The pattern ("cart", "maps", "home") has score 1 (james).
The pattern ("home", "home", "home") has score 0 (no user visited home 3 times).

Example 2:

Input: username = ["ua","ua","ua","ub","ub","ub"], timestamp = [1,2,3,4,5,6], website = ["a","b","a","a","b","c"]
Output: ["a","b","a"]

Constraints:

• 3 <= username.length <= 50
• 1 <= username[i].length <= 10
• timestamp.length == username.length
• 1 <= timestamp[i] <= 109
• website.length == username.length
• 1 <= website[i].length <= 10
• username[i] and website[i] consist of lowercase English letters.
• It is guaranteed that there is at least one user who visited at least three websites.
• All the tuples [username[i], timestamp[i], website[i]] are unique.

---

Solution:

1.

 def mostVisitedPattern(self, username, timestamp, website):
        dp = collections.defaultdict(list)
        for t, u, w in sorted(zip(timestamp, username, website)):
            dp[u].append(w)
        count = sum([collections.Counter(set(itertools.combinations(dp[u], 3))) for u in dp], collections.Counter())
        return list(min(count, key=lambda k: (-count[k], k)))

2.

from collections import defaultdict
from itertools import combinations
class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        
        packed_tuple = zip(timestamp, username, website)   # ---> [(3, 'joe', 'career'),....]
        sorted_packed_tuple = sorted(packed_tuple)  # sort by timestamp, as it didn't say timestamp is sorted array
                                                    # By default tuple always being sorted by the first item
                                                       
        mapping = defaultdict(list)
        for t, u, w in sorted_packed_tuple: # joe: ['home', 'about', 'career']  websites in list are in ascending timestamp order
            mapping[u].append(w)
        
        counter_dict = defaultdict(int)         # use a dict for counting
        for website_list in mapping.values():
            combs = set(combinations(website_list, 3))    # size of combination is set to 3, for details see bottom
            for comb in combs:
                counter_dict[comb] += 1       # Tuple as key, counter as value,  e.g. ('home', 'about', 'career') : 2
        
        sorted_counter_dict = sorted(counter_dict, key=lambda x: (-counter_dict[x], x)) # sort descending by value, then lexicographically
        return sorted_counter_dict[0]

I know most python guys know them well and good at reading compacted 1-line python code. I would like to break it down a little bit. I actually spent 1 hour to try those python packages. “Counter” looks more like dict.. and “combination” is to return an array of different combinations. Hope the code below might help people who would like to read. (Interesting enough I didn’t know we can put “dict” into sorted(), and only return keys as an array).

Update:
Breakdown of combs = set(combinations(website_list, 3))
combinations(['a', 'b', 'c', 'd', 'c'], 3) =>
('a', 'b', 'c') duplicate
('a', 'b', 'd')
('a', 'b', 'c') duplicate
('a', 'c', 'd')
('a', 'c', 'c')
('a', 'd', 'c')
('b', 'c', 'd')
('b', 'c', 'c')
('b', 'd', 'c')
('c', 'd', 'c')
All websites are visited by one user, you can say the user's visited pattern is 'a' -> 'b' -> 'c', you can also say the user's visited pattern 'a' -> 'b' -> 'd'.
The website list is already in ascending timestamp order, so all combinations results are in the same ascending order.
Finally, we need to use set() to dedupe as duplicated patterns visited by one user being counted as 1 score.