1152. Analyze User Website Visit Pattern

T: O(n^3)

S: O(n)

class Solution {
    class WebData {
        String website;
        int timestamp;
        WebData(String website, int timestamp) {
            this.website = website;
            this.timestamp = timestamp;
        }
        
    }
    public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
        int n = username.length;
        Map<String, List<WebData>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(username[i], new ArrayList<>());
            map.get(username[i]).add(new WebData(website[i], timestamp[i]));
        }
        
        Map<String, Integer> countMap = new HashMap<>();
        String res = "";
        for (String name : map.keySet()) {
            // why set, 因為一樣的 name, 如果出現一樣的 pattern, 只能算一次, 所以同一個 name 在計算時, 避免一樣的 pattern 被重複計算
            // 到下個name 時, set 就重置了
            Set<String> set = new HashSet<>();
            List<WebData> list = map.get(name);
            Collections.sort(list, (a, b) -> a.timestamp - b.timestamp); // 還是需要排序, 測資timstamp可能不有序
            
            // 因為 pattern 是三個website組成的, 所以像 james 有 4個網站 "home","cart","maps","home"
            // 這樣要 4取3去排列組合出來所有可能的 pattern, naive 就是跑 n^3
            for (int i = 0; i < list.size(); i++) {
                for (int j = i+1; j < list.size(); j++) {
                    for (int k = j+1; k < list.size(); k++) {
                        String pattern = list.get(i).website + " " + list.get(j).website + " " + list.get(k).website;
                        if (!set.contains(pattern)) {
                            countMap.put(pattern, countMap.getOrDefault(pattern, 0)+1); // 不同name, 一樣的 pattern count++ 
                            set.add(pattern); //避免一樣name, 一樣的pattern 被重複計算
                        }
                        // res 還沒值時, 給個pattern
                        // 新的 pattern count 比較大時, 更新
                        // count 一樣的時候 用 lexicographically smallest such pattern
                        if ("".equals(res) || countMap.get(pattern) > countMap.get(res) || 
                           (countMap.get(pattern) == countMap.get(res) && res.compareTo(pattern) > 0)) {
                            res = pattern;
                        }
                    }
                }
            }
        }
        
        return Arrays.asList(res.split(" ")); // 回傳這唯一的 pattern
        
    }
}

/*
["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].


home about career
"home","cart","maps","home"
"home","about","career"

map
<name, pattern list>

-> pattern list should sort by timestamp

for each name
get list by name
build pattern use loop n^3 (exclude deplicate pattern count in same name), if another name deplicate pattern count is ok


at last if count is same, use lexicographically smallest such pattern


at last, only one pattern is the output

T: O(n^3)
*/

```java
class Solution {
    private record WebHistory(String website, int timestamp) {};
    public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
        Map<String, List<WebHistory>> nameToHistory = new HashMap<>();
        Map<String, Integer> visitedCount = new HashMap<>();
        for (int i = 0; i < username.length; i++) {
            nameToHistory.computeIfAbsent(username[i], k -> new ArrayList<>()).add(new WebHistory(website[i], timestamp[i]));
        }

        String maxPattern = "";
        int max = 0;
        for (String name : nameToHistory.keySet()) { // worst 1 (if only one name
            List<WebHistory> history = nameToHistory.get(name);
            history.sort((a, b) -> a.timestamp - b.timestamp); // worst nlogn (only one name, time len are n)
            
            Set<String> set = new HashSet<>(); // remember don't count duplicated pattern for same name
            for (int i = 0; i < history.size()-2; i++) { // O(n^3)
                for (int j = i+1; j < history.size()-1; j++) {
                    for (int k = j+1; k < history.size(); k++) {

                        StringBuilder websites = new StringBuilder();
                        websites.append(history.get(i).website).append(" ")
                            .append(history.get(j).website).append(" ")
                            .append(history.get(k).website);
                        String pattern = websites.toString();
                        if (!set.contains(pattern)) {
                            visitedCount.put(pattern, visitedCount.getOrDefault(pattern, 0)+1);   
                            set.add(pattern);                
                        }
                        // compare immideiatly is faster than sort all later
                        if ("".equals(maxPattern) || visitedCount.get(pattern) > max
                            || visitedCount.get(pattern) == max && maxPattern.compareTo(pattern) > 0) {
                            maxPattern = pattern;
                            max = visitedCount.get(pattern);
                        }
                    }
                }
            }
        }

        // List<String> result = new ArrayList<>(visitedCount.keySet());
        // result.sort((a, b) -> {
        //     if (visitedCount.get(a) == visitedCount.get(b)) {
        //         return a.compareTo(b);
        //     }
        //     return visitedCount.get(b) - visitedCount.get(a);
        // });
        List<String> res = new ArrayList<>();
        for (String str : maxPattern.split(" ")) {
            res.add(str);
        }
        return res;
    }
}

/***
T: O(nlogn + n^3..) 
S: O(n)

name pattern_list

pattern_list_3, count

 */
```