Question

1152. Analyze User Website Visit Pattern

中文文档

Description

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.

Solutions

Solution 1: Hash Table + Sorting

First, we use a hash table $d$ to record the websites each user visits. Then we traverse $d$. For each user, we enumerate all the triplets they visited, count the occurrence of distinct triplets, and finally traverse all triplets, returning the one with the highest occurrence and the smallest lexicographic order.

The time complexity is $O(n^3)$, and the space complexity is $O(n^3)$. Here, $n$ is the length of username.

class Solution:
  def mostVisitedPattern(
    self, username: List[str], timestamp: List[int], website: List[str]
  ) -> List[str]:
    d = defaultdict(list)
    for user, _, site in sorted(
      zip(username, timestamp, website), key=lambda x: x[1]
    ):
      d[user].append(site)

    cnt = Counter()
    for sites in d.values():
      m = len(sites)
      s = set()
      if m > 2:
        for i in range(m - 2):
          for j in range(i + 1, m - 1):
            for k in range(j + 1, m):
              s.add((sites[i], sites[j], sites[k]))
      for t in s:
        cnt[t] += 1
    return sorted(cnt.items(), key=lambda x: (-x[1], x[0]))[0][0]

class Solution {
  public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
    Map<String, List<Node>> d = new HashMap<>();
    int n = username.length;
    for (int i = 0; i < n; ++i) {
      String user = username[i];
      int ts = timestamp[i];
      String site = website[i];
      d.computeIfAbsent(user, k -> new ArrayList<>()).add(new Node(user, ts, site));
    }
    Map<String, Integer> cnt = new HashMap<>();
    for (var sites : d.values()) {
      int m = sites.size();
      Set<String> s = new HashSet<>();
      if (m > 2) {
        Collections.sort(sites, (a, b) -> a.ts - b.ts);
        for (int i = 0; i < m - 2; ++i) {
          for (int j = i + 1; j < m - 1; ++j) {
            for (int k = j + 1; k < m; ++k) {
              s.add(sites.get(i).site + "," + sites.get(j).site + ","
                + sites.get(k).site);
            }
          }
        }
      }
      for (String t : s) {
        cnt.put(t, cnt.getOrDefault(t, 0) + 1);
      }
    }
    int mx = 0;
    String t = "";
    for (var e : cnt.entrySet()) {
      if (mx < e.getValue() || (mx == e.getValue() && e.getKey().compareTo(t) < 0)) {
        mx = e.getValue();
        t = e.getKey();
      }
    }
    return Arrays.asList(t.split(","));
  }
}

class Node {
  String user;
  int ts;
  String site;

  Node(String user, int ts, String site) {
    this.user = user;
    this.ts = ts;
    this.site = site;
  }
}

class Solution {
public:
  vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) {
    unordered_map<string, vector<pair<int, string>>> d;
    int n = username.size();
    for (int i = 0; i < n; ++i) {
      auto user = username[i];
      int ts = timestamp[i];
      auto site = website[i];
      d[user].emplace_back(ts, site);
    }
    unordered_map<string, int> cnt;
    for (auto& [_, sites] : d) {
      int m = sites.size();
      unordered_set<string> s;
      if (m > 2) {
        sort(sites.begin(), sites.end());
        for (int i = 0; i < m - 2; ++i) {
          for (int j = i + 1; j < m - 1; ++j) {
            for (int k = j + 1; k < m; ++k) {
              s.insert(sites[i].second + "," + sites[j].second + "," + sites[k].second);
            }
          }
        }
      }
      for (auto& t : s) {
        cnt[t]++;
      }
    }
    int mx = 0;
    string t;
    for (auto& [p, v] : cnt) {
      if (mx < v || (mx == v && t > p)) {
        mx = v;
        t = p;
      }
    }
    return split(t, ',');
  }

  vector<string> split(string& s, char c) {
    vector<string> res;
    stringstream ss(s);
    string t;
    while (getline(ss, t, c)) {
      res.push_back(t);
    }
    return res;
  }
};

func mostVisitedPattern(username []string, timestamp []int, website []string) []string {
  d := map[string][]pair{}
  for i, user := range username {
    ts := timestamp[i]
    site := website[i]
    d[user] = append(d[user], pair{ts, site})
  }
  cnt := map[string]int{}
  for _, sites := range d {
    m := len(sites)
    s := map[string]bool{}
    if m > 2 {
      sort.Slice(sites, func(i, j int) bool { return sites[i].ts < sites[j].ts })
      for i := 0; i < m-2; i++ {
        for j := i + 1; j < m-1; j++ {
          for k := j + 1; k < m; k++ {
            s[sites[i].site+","+sites[j].site+","+sites[k].site] = true
          }
        }
      }
    }
    for t := range s {
      cnt[t]++
    }
  }
  mx, t := 0, ""
  for p, v := range cnt {
    if mx < v || (mx == v && p < t) {
      mx = v
      t = p
    }
  }
  return strings.Split(t, ",")
}

type pair struct {
  ts   int
  site string
}