/**
1. 首先建立Trie提供快速前缀搜索, 搜索后缀合并时维护下顺序

3. 怎么对应前缀的所有字符串? 
3.1 需求: a.优先频率 b.频率相等字典序最小
3.2 设计: 
    3.2.1 Trie的子节点 空格应该在字母前,这样直接保证了先序遍历的时候字典序最小
    3.2.2 因为是按字符输入的, 所以每次缓存前缀时也缓存下对应Trie的节点, 直接向下搜索即可
    3.2.3 求top3 在维护结果集时插入排序求下即可, 因为数量很少,所以最多多一次操作, 如果用最小堆还需用Node包装后重写compare

*/

class AutocompleteSystem {

    class Trie{

        boolean isWord;
        Trie[] childs;

        public Trie(){
            this.childs = new Trie[27];
            this.isWord = false;
        }
        public int c2i(char c) {return c == ' '? 0 : c - 'a' + 1;}
        public char i2c(int i) {return i == 0 ? ' ' : (char)('a' + i - 1);}


        void add(String s){
            Trie p = this;
            for (int i = 0; i < s.length();  i++){
                char c = s.charAt(i);
                int index = c2i(c);
                if (p.childs[index] == null) p.childs[index] = new Trie();
                p = p.childs[index];
            }
            p.isWord = true;
        }

        List<String> search(Trie p, StringBuilder buffer){
            List<String> res = new ArrayList<String>();
            if (p == null) return res;
            getSuffix(res, p, buffer);
            return res;
        }

        private void getSuffix(List<String> res, Trie p, StringBuilder buffer){
            if (p.isWord) {
                res.add(buffer.toString());
                for (int i = res.size()-1 ; i >= 1; i--){
                    if (freq.get(res.get(i)) > freq.get(res.get(i-1)))  Collections.swap(res, i, i-1);
                    else break;
                }
                while(res.size() > 3) res.remove(res.size()-1);
            }
            for (int i = 0 ; i < p.childs.length; i++){
                if (p.childs[i] != null) {
                    char c = i2c(i);
                    buffer.append(c);
                    getSuffix(res, p.childs[i], buffer);
                    if (buffer.length() > 0 ) buffer.setLength(buffer.length()-1);
                }
            }
        }
    }

    Trie trie, last;
    Map<String, Integer> freq;
    StringBuilder buffer;

    public AutocompleteSystem(String[] sentences, int[] times) {
        this.trie =  new Trie();
        this.last = trie;
        this.freq = new HashMap<>();
        this.buffer = new StringBuilder();

        for (int i = 0 ; i < sentences.length ; i++){
            trie.add(sentences[i]);
            freq.put(sentences[i], times[i]);
        }
    }

    public List<String> input(char c) {
        if (c == '#'){
            String word = buffer.toString();
            if (! freq.containsKey(word)) freq.put(word, 0);
            freq.put(word, freq.get(word) + 1);
            trie.add(word);
            buffer.setLength(0);
            this.last = trie;
            return new ArrayList<String>();
        }
        buffer.append(c);
        int index = trie.c2i(c);
        last = last == null ? null : last.childs[index];
        return trie.search(last, buffer);
    }
}

/**
 * Your AutocompleteSystem object will be instantiated and called as such:
 * AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
 * List<String> param_1 = obj.input(c);
 */