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.
Both username[i] and website[i] contain only lowercase characters.
It is guaranteed that there is at least one user who visited at least 3 websites.
No user visits two websites at the same time.
Solution:
class Solution {
static class Entry {
String user;
int time;
String website;
public Entry(String user, int time, String website) {
this.user = user;
this.time = time;
this.website = website;
}
}
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
Map<String, Map<Integer, List<List<String>>>> map = new HashMap();
Map<List<String>, Set<String>> count = new HashMap();
List<Entry> visits = new ArrayList();
for (int i = 0; i < username.length; i ++) {
visits.add(new Entry(username[i], timestamp[i], website[i]));
}
Collections.sort(visits, (a, b) -> a.time - b.time);
for (int i = 0; i < visits.size(); i ++) {
Entry visit = visits.get(i);
map.putIfAbsent(visit.user, new HashMap());
Map<Integer, List<List<String>>> visitMap = map.get(visit.user);
visitMap.putIfAbsent(2, new ArrayList());
List<List<String>> prev = visitMap.get(2);
for (List<String> p : prev) {
List<String> n = new ArrayList(p);
n.add(visit.website);
count.putIfAbsent(n, new HashSet());
count.get(n).add(visit.user);
}
visitMap.putIfAbsent(1, new ArrayList());
prev = visitMap.get(1);
List<List<String>> next = new ArrayList();
for (List<String> p : prev) {
List<String> n = new ArrayList(p);
n.add(visit.website);
next.add(n);
}
visitMap.get(2).addAll(next);
List<String> one = new ArrayList();
one.add(visit.website);
visitMap.get(1).add(one);
}
List<String> result = new ArrayList();
int max = 0;
for (Map.Entry<List<String>, Set<String>> entry : count.entrySet()) {
if (entry.getValue().size() > max) {
max = entry.getValue().size();
result = entry.getKey();
} else if (entry.getValue().size() == max) {
for (int i = 0; i < result.size(); i ++) {
String a = entry.getKey().get(i);
String b = result.get(i);
// System.out.println(a + "#" + b);
if (a.compareTo(b) < 0) {
result = entry.getKey();
break;
} else if (a.compareTo(b) == 0) {
continue;
} else {
break;
}
}
}
}
// System.out.println(count);
// System.out.println(map);
return result;
}
}