1152.Analyze user website visit pattern

We are given some website visits: the user with name username[i] visited the website website[i] at time timestamp[i].

A 3-sequence is a list of websites of length 3 sorted in ascending order by the time of their visits. (The websites in a 3-sequence are not necessarily distinct.)

Find the 3-sequence visited by the largest number of users. If there is more than one solution, return the lexicographically smallest such 3-sequence.

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", 1, "home"]
["joe", 2, "about"]
["joe", 3, "career"]
["james", 4, "home"]
["james", 5, "cart"]
["james", 6, "maps"]
["james", 7, "home"]
["mary", 8, "home"]
["mary", 9, "about"]
["mary", 10, "career"]
The 3-sequence ("home", "about", "career") was visited at least once by 2 users.
The 3-sequence ("home", "cart", "maps") was visited at least once by 1 user.
The 3-sequence ("home", "cart", "home") was visited at least once by 1 user.
The 3-sequence ("home", "maps", "home") was visited at least once by 1 user.
The 3-sequence ("cart", "maps", "home") was visited at least once by 1 user.

Note:

1. 3 <= N = username.length = timestamp.length = website.length <= 50

2. 1 <= username[i].length <= 10

3. 0 <= timestamp[i] <= 10^9

4. 1 <= website[i].length <= 10

5. Both username[i] and website[i] contain only lowercase characters.

6. It is guaranteed that there is at least one user who visited at least 3 websites.

7. No user visits two websites at the same time.

Solution:

version 1: Brute Force

https://www.youtube.com/watch?v=V510Lbtrm5s Map<String, TreeMap<Integer, String>> map;

form the all 3-sequence from a user, concat is into a string (use 3 for loop)

Map<String, Integer> freqMap

String is the concat string, like "home->about->career" , Integer is the freq.

class Solution {
 2     public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
 3         int n = username.length;
 4         List<Pair> datas = new ArrayList<>();
 5         for(int i = 0; i < n; i++){
 6             datas.add(new Pair(username[i], timestamp[i], website[i]));
 7         }
 8         
 9         Collections.sort(datas, (a, b) -> a.time - b.time);
10         HashMap<String, List<String>> userToWebs = new HashMap<>();
11         for(Pair data : datas){
12             userToWebs.putIfAbsent(data.user, new ArrayList<String>());
13             userToWebs.get(data.user).add(data.web);
14         }
15         
16         HashMap<String, Integer> seqToCount = new HashMap<>();
17         
18         int maxCount = 0;
19         String maxSeq = "";
20         for(Map.Entry<String, List<String>> entry : userToWebs.entrySet()){
21             Set<String> seqCom = getCom(entry.getValue());
22             for(String seq : seqCom){
23                 seqToCount.put(seq, seqToCount.getOrDefault(seq, 0) + 1);
24                 if(seqToCount.get(seq) > maxCount){
25                     maxCount = seqToCount.get(seq);
26                     maxSeq = seq;
27                 }else if(seqToCount.get(seq) == maxCount && seq.compareTo(maxSeq) < 0){
28                     maxSeq = seq;
29                 }    
30             }
31         }
32         
33         List<String> res = new ArrayList<>();
34         String [] webs = maxSeq.split(",");
35         for(String w : webs){
36             res.add(w);
37         }
38         
39         return res;
40     }
41     
42     private HashSet<String> getCom(List<String> webs){
43         HashSet<String> res = new HashSet<>();
44         int n = webs.size();
45         for(int i = 0; i < n - 2; i++){
46             for(int j = i + 1; j < n - 1; j++){
47                 for(int k = j + 1; k < n; k++){
48                     res.add(webs.get(i) + "," + webs.get(j) + "," + webs.get(k));
49                 }
50             }
51         }
52         
53         return res;
54     }
55 }
56 
57 class Pair{
58     String user;
59     int time;
60     String web;
61     public Pair(String user, int time, String web){
62         this.user = user;
63         this.time = time;
64         this.web = web;
65     }

This is similar to a Amazon interview: https://leetcode.com/discuss/interview-question/420704/amazon-most-popular-page-sequence

The diff is the amazon question , the timestamp must be consecutive, like 1,2,3 2,3,4 3,4,5.

But in the question timestamp can be non-consecutive.