Skip to content

3527. Find the Most Common Response

You are given a 2D string array responses where each responses[i] is an array of strings representing survey responses from the ith day.

Return the most common response across all days after removing duplicate responses within each responses[i]. If there is a tie, return the lexicographically smallest response.

A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one.

Example 1:

Input: responses = [["good","ok","good","ok"],["ok","bad","good","ok","ok"],["good"],["bad"]]

Output: "good"

Explanation:

  • After removing duplicates within each list, responses = [["good", "ok"], ["ok", "bad", "good"], ["good"], ["bad"]].
  • "good" appears 3 times, "ok" appears 2 times, and "bad" appears 2 times.
  • Return "good" because it has the highest frequency.

Example 2:

Input: responses = [["good","ok","good"],["ok","bad"],["bad","notsure"],["great","good"]]

Output: "bad"

Explanation:

  • After removing duplicates within each list we have responses = [["good", "ok"], ["ok", "bad"], ["bad", "notsure"], ["great", "good"]].
  • "bad", "good", and "ok" each occur 2 times.
  • The output is "bad" because it is the lexicographically smallest amongst the words with the highest frequency.

Constraints:

  • 1 <= responses.length <= 1000
  • 1 <= responses[i].length <= 1000
  • 1 <= responses[i][j].length <= 10
  • responses[i][j] consists of only lowercase English letters

Solution:

class Solution {
    public String findCommonResponse(List<List<String>> responses) {
        // PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((e1, e2) -> {
            if (!e1.getValue().equals(e2.getValue())){
                return e2.getValue() - e1.getValue();
            }
            return e1.getKey().compareTo(e2.getKey());
        });
        // PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
        //     new Comparator<Map.Entry<String, Integer>>(){
        //         public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2){
        //             if (e1.getValue() > e2.getValue()){
        //                 return -1;
        //             }else if (e1.getValue() < e2.getValue()){
        //                 return 1;
        //             }else{
        //                 int chare1 = e1.getKey().charAt(0) - 'a';
        //                 int chare2 = e2.getKey().charAt(0) - 'a';

        //                 if (chare1 < chare2){
        //                     return -1;
        //                 }else if (chare1 > chare2){
        //                     return 1;
        //                 }else{
        //                     if (e1.getKey().length() < e2.getKey().length()){
        //                         return -1;
        //                     }else if (e1.getKey().length() > e2.getKey().length()) {
        //                         return 1;
        //                     }else{
        //                         if (e1.getKey().length() == 1){
        //                             return 0;
        //                         }else{
        //                             int charE1 = e1.getKey().charAt(1) - 'a';
        //                             int charE2 = e2.getKey().charAt(1) - 'a';
        //                             if (charE1 < charE2){
        //                                 return -1;
        //                             }else{
        //                                 return 1;
        //                             }
        //                         }
        //                     }
        //                 }
        //             }

        //         }
        //     }
        // );
        // max heap
        List<Set<String>> newResponses = new ArrayList<>();

        for (List<String> l : responses){
            Set<String> cur = new HashSet<>();
            for (String s : l){
                cur.add(s);
            }

            newResponses.add(cur);

        }

        Map<String, Integer> map = new HashMap<>();
        for (Set<String> s : newResponses){
            for (String str : s){
                if (map.containsKey(str)){
                    map.put(str, map.get(str) + 1);
                }else{
                    map.put(str, 1);
                }
            }
        }


        for (Map.Entry<String, Integer> e : map.entrySet()){
            pq.offer(e);
        }


        return pq.peek().getKey();
    }
}