Design Search Autocomplete System

import java.util.*;

class AutocompleteSystem {
    private final Map<String, Integer> counts = new HashMap<>();
    private final StringBuilder prefix = new StringBuilder();

    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) counts.merge(sentences[i], times[i], Integer::sum);
    }

    public List<String> input(char c) {
        if (c == '#') {
            counts.merge(prefix.toString(), 1, Integer::sum);
            prefix.setLength(0);
            return new ArrayList<>();
        }
        prefix.append(c);
        String p = prefix.toString();
        List<String> matches = new ArrayList<>();
        for (String s : counts.keySet()) if (s.startsWith(p)) matches.add(s);
        matches.sort((a, b) -> !counts.get(a).equals(counts.get(b)) ? counts.get(b) - counts.get(a) : a.compareTo(b));
        return new ArrayList<>(matches.subList(0, Math.min(3, matches.size())));
    }
}

import java.util.*;

class AutocompleteSystem {
    private static class Node {
        final Map<Character, Node> next = new HashMap<>();
        final Map<String, Integer> counts = new HashMap<>();     // sentences passing through
    }

    private final Node root = new Node();
    private Node cur = root;
    private final StringBuilder prefix = new StringBuilder();

    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) add(sentences[i], times[i]);
    }

    private void add(String s, int t) {
        Node n = root;
        for (char ch : s.toCharArray()) {
            n = n.next.computeIfAbsent(ch, k -> new Node());
            n.counts.merge(s, t, Integer::sum);
        }
    }

    public List<String> input(char c) {
        if (c == '#') {
            add(prefix.toString(), 1);
            prefix.setLength(0);
            cur = root;
            return new ArrayList<>();
        }
        prefix.append(c);
        cur = cur == null ? null : cur.next.get(c);
        if (cur == null) return new ArrayList<>();
        Map<String, Integer> m = cur.counts;
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> !m.get(a).equals(m.get(b)) ? m.get(a) - m.get(b) : b.compareTo(a));
        for (String s : m.keySet()) {
            pq.offer(s);
            if (pq.size() > 3) pq.poll();                        // keep the best 3
        }
        LinkedList<String> out = new LinkedList<>();
        while (!pq.isEmpty()) out.addFirst(pq.poll());
        return out;
    }
}