Leetcode 1152: Analyze User Website Visit Pattern

https://leetcode.com › problems › analyse-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.

Notes:

After reading this question several times, I still cannot get the point of this question. Roughly it is asking for the top 3 rank of three-websites comb visited. One of the requirement is that these three website must be visited by the same person, and then it is counted as 1.

There is no much algorithm involved, and it is question for date structure.

First step, we can built up a map: the key will include the person. And we need to know all the websites the person has visited. A person may visit the same website several times but at different times, so the visiting time can also be used as one part of the key. In this way, we can record the combos composing with the same website but visited at different time.

The next step will be building all the possible three-website combos for the same person.

Then we can save this result using another map, but this time the three-website combo are the key. Thus we cannot use unordered_map if we use a string vector as the key.

We still need to know which person visits this three-website combo, so person can again be one part of the key for labeling.

After this map is finished, we just need to find the one with the largest counting.

See the code below:

vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) {
    int len = username.size();
    unordered_map<string,map<int,string>> data;
    for(int i=0; i<len; ++i) {
        data[username[i]][timestamp[i]] = website[i];
    }
    map<vector<string>,unordered_map<string,int>> cts;
    for(auto &d : data) {
        if(d.second.size()<3) continue;
        for(auto i=d.second.begin(); i!=d.second.end(); ++i) {
            auto j = i; j++;
            for(; j!=d.second.end(); ++j) {
                auto k = j; k++;
                for(; k!=m.second.end(); ++k) {
                    ++cts[{(*i).second,(*j).second,(*k).second}][d.first];
                }
            }
        }
    }
    vector<string> res;
    int largest = 0;
    for(auto &i : cts){
        if(i.second.size() > largest){
            res = i.first;
            largest = i.second.size();
        }
    }
    return res;
}

A good reference can be found here:

https://github.com/ScientificKnights/Leetcode-Templates-and-Examples/blob/master/code/1152.%20Analyze%20User%20Website%20Visit%20Pattern.h