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.

Rust Solution

struct Solution;
use std::collections::HashMap;
use std::collections::HashSet;

type Sequence = (String, String, String);

impl Solution {
    fn most_visited_pattern(
        mut username: Vec<String>,
        mut timestamp: Vec<i32>,
        mut website: Vec<String>,
    ) -> Vec<String> {
        let mut hm: HashMap<String, Vec<(i32, String)>> = HashMap::new();
        let mut sequences: HashMap<Sequence, HashSet<String>> = HashMap::new();
        while let (Some(u), Some(t), Some(w)) = (username.pop(), timestamp.pop(), website.pop()) {
            hm.entry(u).or_default().push((t, w));
        }
        for (u, p) in hm.iter_mut() {
            p.sort_unstable_by_key(|p| p.0);
            let n = p.len();
            for i in 0..n {
                for j in i + 1..n {
                    for k in j + 1..n {
                        let sequence = (p[i].1.to_string(), p[j].1.to_string(), p[k].1.to_string());
                        sequences.entry(sequence).or_default().insert(u.to_string());
                    }
                }
            }
        }
        let mut max = 0;
        let mut res = ("".to_string(), "".to_string(), "".to_string());
        for (sequence, hs) in sequences {
            if hs.len() > max {
                max = hs.len();
                res = sequence;
            } else if hs.len() == max && sequence < res {
                res = sequence;
            }
        }
        vec![res.0, res.1, res.2]
    }
}

#[test]
fn test() {
    let username = vec_string![
        "joe", "joe", "joe", "james", "james", "james", "james", "mary", "mary", "mary"
    ];
    let timestamp = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    let website = vec_string![
        "home", "about", "career", "home", "cart", "maps", "home", "home", "about", "career"
    ];
    let res = vec_string!["home", "about", "career"];
    assert_eq!(
        Solution::most_visited_pattern(username, timestamp, website),
        res
    );
}

Having problems with this solution? Click here to submit an issue on github.