Lintcode 1208. Target Sum

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Example 2:

Input: nums is [], S is 3. 
Output: 0
Explanation: 
There are 0 way to assign symbols to make the sum of nums be target 3.

Notice

1. The length of the given array is positive and will not exceed 20.
2. The sum of elements in the given array will not exceed 1000.
3. Your output answer is guaranteed to be fitted in a 32-bit integer.

Solution:
Backpacking DP problem.

Code (Java):

public class Solution {
    /**
     * @param nums: the given array
     * @param s: the given target
     * @return: the number of ways to assign symbols to make sum of integers equal to target S
     */
    public int findTargetSumWays(int[] nums, int s) {
        // Write your code here
        
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        if (s > Math.abs(sum)) {
            return 0;
        }
        
        int[][] dp = new int[nums.length + 1][2 * sum + 1];
        dp[0][sum] = 1; // index = num + sum;
        
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j < 2 * sum + 1; j++) {
                if (j - nums[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]];
                }
                
                if (j + nums[i - 1] < 2 * sum + 1) {
                    dp[i][j] += dp[i - 1][j + nums[i - 1]];
                }
            }
        }
        
        return dp[nums.length][s + sum];
    }
}

Lintcode 1817. Divide Chocolate

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.

You want to share the chocolate with your K friends so you start cutting the chocolate bar into K+1 pieces using K cuts, each piece consists of some consecutive chunks.

Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.

Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

Example

Example 1:

Input: sweetness = [1,2,3,4,5,6,7,8,9], K = 5
Output: 6
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]

Example 2:

Input: sweetness = [5,6,7,8,9,1,2,3,4], K = 8
Output: 1
Explanation: There is only one way to cut the bar into 9 pieces.

Example 3:

Input: sweetness = [1,2,2,1,2,2,1,2,2], K = 2
Output: 5
Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]

Notice

• 0 <= K < sweetness.length <= 10^4
• 1 <= sweetness[i] <= 10^5

 

Solution:

Binary search on answer. 

The idea is if we give a larger sweetness to each person, they tend to have more pieces each one, so the number of people we can distribute tend to be less. The same to the other. If a person gets less sweetness, we can distribute to more people.

So the idea is, given a sweetness level, we can find out the number of people we can distribute to. If it's less than the K + 1, that means the sweentess we choose was too high; otherwise, if the number of people is greater or equal to the K + 1, we can try a bigger sweetness.

Code (Java):

public class Solution {
    /**
     * @param sweetness: an integer array
     * @param K: an integer
     * @return:  return the maximum total sweetness of the piece
     */
    public int maximizeSweetness(int[] sweetness, int K) {
        // write your code here
        if (sweetness == null || sweetness.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = 0;
        
        for (int s : sweetness) {
            lo = Math.min(lo, s);
            hi += s;
        }
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (getNumFriends(sweetness, mid) >= K + 1) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        
        if (getNumFriends(sweetness, hi) >= K + 1) {
            return hi;
        }
        
        return lo;
    }
    
    private int getNumFriends(int[] sweetness, int s) {
        int count = 0;
        int curr = 0;
        
        for (int sweet : sweetness) {
            curr += sweet;
            if (curr >= s) {
                count++;
                curr = 0;
            }
        }
        
        return count;
    }
}

Lintcode 1379. The Longest Scene

A string, each character representing a scene. Between two identical characters is considered to be a continuous scene. For example: abcda, you can think of these five characters as the same scene. Or acafghbeb can think of two aca and beb scenes. If there is a coincidence between the scenes, then the scenes are combined. For example, abcab, where abca and bcab are coincident, then the five characters are considered to be the same scene. Give a string to find the longest scene.

Example

Example 1

Input: "abcda"
Output: 5
Explanation:
The longest scene is "abcda".

Example 2

Input: "abcab"
Output: 5
Explanation:
The longest scene is "abcab".

Notice

• 1 <= |str| <=1e5
• str contains only lowercase letters

Solution:

First of all, for each character, we note down the position of the rightmost same character it can reach. E.g. abcdad. For character a, the position of the rightmost is 4. 

After that, we can form a list of intervals with start and end position of each character. Then the problem is to merge the intervals. 

Code (Java):

 

public class Solution {
    /**
     * @param str: The scene string
     * @return: Return the length longest scene
     */
    public int getLongestScene(String str) {
        // Write your code here
        if (str == null || str.length() == 0) {
            return 0;
        }
        
        if (str.length() == 1) {
            return 1;
        }
        
        // pos saves the rightmost position of each character
        int[] pos = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            pos[c - 'a'] = i;
        }
        
        // store the intervals into the list. Note that it's already sorted by the start time
        List<Interval> intervals = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (pos[c - 'a'] != i) {
                intervals.add(new Interval(i, pos[c - 'a']));
            }
        }
        
        // now it's time to merge and get the longest interval
        Interval prev = null;
        int ans = 1;
        
        for (int i = 0; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (prev == null || prev.end < curr.start) {
                prev = curr;
            } else { // overlap
                prev.start = Math.min(prev.start, curr.start);
                prev.end = Math.max(prev.end, curr.end);
            }
            
            if (prev.end - prev.start + 1 > ans) {
                ans = prev.end - prev.start + 1;
            }
        }
        
        if (prev != null) {
            ans = Math.max(ans, prev.end - prev.start + 1);
        }
        
        return ans;
        
    }
}

class Interval {
    int start;
    int end;
    
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

Lintcode1399. Take Coins

1399. Take Coins

中文English

There aren coins in a row, each time you want to take a coin from the left or the right side. Take a total of k times to write an algorithm to maximize the value of coins.

Example

Example 1:

Input: list = [5,4,3,2,1], k = 2
Output :9
Explanation:Take two coins from the left.

Example 2:

Input: list = [5,4,3,2,1,6], k = 3, 
Output:15
Explanation:Take two coins from the left and one from the right.

Notice

• 1 <= k <= n <= 100000。
• The value of the coin is not greater than 10000。

Wrong solution:

Greedy. Two pointers from the start and end of the array, respectively. Each time get the larger value until k times. The reason it doesn't work is one example [4, 1, 1, 1, 6, 1] and k = 2. For the greedy. We take 4 and 1, so the value is 5. However, the max value we can get is to get 6 and 1, which is 7 instead. 

Correct Solution:

The correct solution is we can take k from left, then 0 from right, e.g.

from left      from  right

k                     0

k - 1                1

k - 2                2

...                    ...

0                     k

So the solution is we first get sum of the first k elements from the left. And then each time we get one from right, we substract from the left side. 

Code (Java):

 

public class Solution {
    /**
     * @param list: The coins
     * @param k: The k
     * @return: The answer
     */
    public int takeCoins(int[] list, int k) {
        // Write your code here
        if (list == null || list.length == 0) {
            return 0;
        }
        
        int sum = 0;
        int maxSum = 0;
        
        int left = 0;
        int right = list.length - 1;
        
        for (left = 0; left < k; left++) {
            sum += list[left];
        }
        
        maxSum = sum;
        
        // left pointer back off by one
        left--;
        
        while (left >= 0) {
            sum -= list[left];
            left--;
            
            sum += list[right];
            right--;
            
            maxSum = Math.max(maxSum, sum);
        }
        
        return maxSum;
    }
}

Lintcode 1390. Short Encoding of Words

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.

What is the length of the shortest reference string S possible that encodes the given words?

Example

**Input**: words = ["time", "me", "bell"]
**Output**: 10
**Explanation**: S = "time#bell#" and indexes = [0, 2, 5].

Notice

• 1 <= words.length <= 2000.
• 1 <= words[i].length <= 7.
• Each word has only lowercase letters.

Solution:

Two words can be compressed if and only if they share the same suffix. For e.g. time, me, ime can be compressed. But time and im cannot be compressed. And time and ame cannot be compressed as well.

So the solution is to use a trie to store all the words in reverse order. In the end, count the number of nodes of the trie and calculate the final length. 

Code (Java):

public class Solution {
    /**
     * @param words: 
     * @return: nothing
     */
    public int minimumLengthEncoding(String[] words) {
        // 
        if (words == null || words.length == 0) {
            return 0;
        }
        
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        
        return trie.getLength();
    }
}

class TrieNode {
    public TrieNode[] children;
    
    public TrieNode() {
        this.children = new TrieNode[26];
    }
}

class Trie {
    private TrieNode root;
    
    public Trie() {
        this.root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode p = root;
        
        for (int i = word.length() - 1; i >= 0; i--) {
            char c = word.charAt(i);
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }
            
            p = p.children[c - 'a'];
        }
    }
    
    public int getLength() {
        TrieNode p = root;
        
        return dfs(p, 0);
    }
    
    private int dfs(TrieNode p, int depth) {
        // if p is a leaf node, get the number and return
        boolean leaf = true;
        
        int len = 0;
        
        for (int i = 0; i < 26; i++) {
            if (p.children[i] != null) {
                leaf = false;
                len += dfs(p.children[i], depth + 1);
            }
        }
        
        if (leaf) {
            len += depth + 1;
        }
        
        return len;
    }
    
}

Lintcode 1430. Similar String Groups

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list A of strings. Every string in A is an anagram of every other string in A. How many groups are there?

Example

Example 1:

Input: ["tars","rats","arts","star"]
Output: 2

Example 2:

Input: ["omv","ovm"]
Output: 1

Clarification

Anagram: a new word formed by changing the position (order) of the letters in a string.

Notice

1.A.length <= 2000
2.A[i].length <= 1000
3.A.length * A[i].length <= 20000
4.All words in A consist of lowercase letters only.

5.All words in A have the same length and are anagrams of each other. 

Solution:

Union-Find. For each of the two words in the list, if they are similar, connect them into the same connected components. In the end, we need to count number of cc. 

Code (Java):

public class Solution {
    /**
     * @param A: a string array
     * @return: the number of groups 
     */
    public int numSimilarGroups(String[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
        
        UF uf = new UF(A);
        
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                if (isSimilar(A[i], A[j])) {
                    uf.connect(A[i], A[j]);
                }
            }
        }
        
        return uf.getNumCC();
    }
    
    private boolean isSimilar(String s1, String s2) {
        int first = -1;
        int second = -1;
        
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            
            if (c1 == c2) {
                continue;
            }
            
            if (first == -1) {
                first = i;
            } else if (second == -1) {
                second = i;
            } else {
                return false;
            }
        }
        
        if (first == -1 && second == -1) {
            return true;
        }
        
        if (s1.charAt(first) == s2.charAt(second) && s1.charAt(second) == s2.charAt(first)) {
            return true;
        }
        
        return false;
    }
}

class UF {
    private Map<String, String> parents;
    private int numCC;
    
    public UF (String[] A) {
        parents = new HashMap<>();
        
        for (String a : A) {
            parents.put(a, a);
        }
        
        numCC = parents.size();
    }
    
    public String find(String a) {
        String root = a;
        
        while (!root.equals(parents.get(root))) {
            root = parents.get(root);
        }
        
        // path compression
        while (!root.equals(a)) {
            String parent = parents.get(a);
            parents.put(a, root);
            a = parent;
        }
        
        return root;
    }
    
    public void connect(String a, String b) {
        String pa = find(a);
        String pb = find(b);
        
        if (!pa.equals(pb)) {
            parents.put(pa, pb);
            numCC--;
        }
    }
    
    public int getNumCC() {
        return numCC;
    }
}

Lintcode 1641. Max Remove Order

Give a m * n board with a value of 0 or 1. At each step we can turn a 1 into 0 if there is another 1 in the same row or column. Return the max number of 1 we can turn into 0.

Example

Example 1:

Input：[[1,1,1,1],[1,1,0,1],[1,0,1,0]]
Output：8
Explanation:
In the board
1, 1, 1, 1
1, 1, 0, 1
1, 0, 1, 0
We can remove 1 from right to left, from bottom to top, until there is only one 1 at (0, 0). Totally 8 removed.

Example 2:

Input：[[1,0],[1,0]]
Output：1
Explanation:
In the board
1, 0
1, 0
We can only remove (0,0) or (1,0)

Notice

n and m do not exceed $50$

Solution:

Use Union Find.

Consider from a simpler example. [1, 1, 1, 1]. We can remove three 1s from the set until the last one. So if we scan from left to right, up to bottom, for each element if the value is 1, we connect to the right-most element from the row and bottom-most element from the column. At the end, how many elements we cannot remove? It's the number of connected components. 

Code (Java):

public class Solution {
    /**
     * @param mp: the board
     * @return: the max number of points we can remove
     */
    public int getAns(int[][] mp) {
        // Write your code here.
        if (mp == null || mp.length == 0) {
            return 0;
        }
        
        int m = mp.length;
        int n = mp[0].length;
        
        int numOnes = 0;
        
        // cols[i]: for ith col, the index of the bottom-most one
        // rows[i], for ith row, the index of the right-most one
        int[] rows = new int[m];
        int[] cols = new int[n];
        
        UF uf = new UF(mp);
        
        // step 1: calculate the number of 1s and the right-most position and 
        // bottom-most position of the 1s
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mp[i][j] == 1) {
                    numOnes++;
                    rows[i] = j;
                    cols[j] = i;
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mp[i][j] == 1) {
                    uf.connect(i * n + j, i * n + rows[i]);
                    uf.connect(i * n + j, cols[j] * n + j);
                }
            }
        }
        
        return numOnes - uf.getNumCC();
        
    }
}

class UF {
    private int[] parents;
    private int numCC;
    
    public UF (int[][] mp) {
        int m = mp.length;
        int n = mp[0].length;
        
        parents = new int[m * n];
    
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mp[i][j] == 1) {
                    parents[i * n + j] = i * n + j;
                    numCC++;
                }
            }
        }
    }
    
    public int find(int a) {
        int root = a;
        
        while (parents[root] != root) {
            root = parents[root];
        }
        
        while (root != a) {
            int parent = parents[a];
            parents[a] = root;
            a = parent;
        }
        
        return root;
    }
    
    public void connect(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        
        if (parents[pa] != pb) {
            parents[pa] = pb;
            numCC--;
        }
    }
    
    public int getNumCC() {
        return numCC;
    }
}

Lintcode 1391. Making A Large Island

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example

Example 1:

Input:[[1, 0], [0, 1]]
Output:3

Explanation:
Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output:4

Explanation:
 Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input:[[1, 1], [1, 1]]
Output:4

Explanation:
 Can't change any 0 to 1, only one island with area = 4.

Notice

• 1 <= grid.length = grid[0].length <= 50.
• 0 <= grid[i][j] <= 1.

Code (Java):

public class Solution {
    /**
     * @param grid: 
     * @return: nothing
     */
    public int largestIsland(int[][] grid) {
        // 
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        UF uf = new UF(m, n, grid);
        
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // step 1: connect all 1s
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] dir : dirs) {
                    int nx = i + dir[0];
                    int ny = j + dir[1];
                    
                    if (grid[i][j] == 1 && nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        uf.union(i * n + j, nx * n + ny);
                    }
                }
            }
        }
        
        int maxSize = 0;
        
        // step 2: find all 0s and try to connect
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int size = 1;
                Set<Integer> parents = new HashSet<>();
                for (int[] dir : dirs) {
                    int nx = i + dir[0];
                    int ny = j + dir[1];
                    
                    if (grid[i][j] == 0 && nx >= 0 && nx < m && ny >=0 && ny < n && grid[nx][ny] == 1) {
                        int parent = uf.getParent(nx * n + ny);
                        if (!parents.contains(parent)) {
                            parents.add(parent);
                            size += uf.getSize(nx * n + ny);
                        }
                    }
                }
                
                maxSize = Math.max(size, maxSize);
            }
        }
        
        return maxSize;
    }
}

class UF {
    int[] parents;
    int[] size;
    int m;
    int n;
    int[][] grid;
    
    public UF (int m, int n, int[][] grid) {
        this.m = m;
        this.n = n;
        this.grid = grid;
        
        parents = new int[m * n];
        size = new int[m * n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                parents[i * n + j] = i * n + j;
                size[i * n + j] = 1;
            }
        }
    }
    
    public void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        
        if (pa != pb) {
            parents[pa] = pb;
            size[pb] += size[pa];
        }
    }
    
    private int find(int a) {
        int root = a;
        
        while (root != parents[root]) {
            root = parents[root];
        }
        
        // path compression
        while (root != a) {
            int parent = parents[a];
            parents[a] = root;
            a = parent;
        }
        
        return root;
    }
    
    public int getSize(int a) {
        int pa = find(a);
        return size[pa];
    }
    
    public int getParent(int a) {
        return find(a);
    }
}

Lintcode 1411. Edit Distance - Replace Edition

Given two strings s1 and s2, find the least number of operations and make the two strings equal.
In this problem, an operation is defined as replace one kind of character to another character indefinitely.

Example

Example 1:

Input: s1 = "abb", s2 = "dad"
Output: 2
Explantion: Then first letters will coincide when we will replace letter 'a' with 'd'. Second letters will coincide when we will replace 'b' with 'a'. Third letters will coincide when we will at first replace 'b' with 'a' and then 'a' with 'd'.

Notice

Two strings with same length consisting only of lowercase English letters.

Solution:

Use Union Find. For each character from s1 to s2, say c1->c2, if there is a change, we connect c1 to c2 in one connected component. 

Code (Java):

public class Solution {
    /**
     * @param s1: a string
     * @param s2: a string
     * @return: the least number of operations and make the two strings equal
     */
    public int editDistance(String s1, String s2) {
        // Write your code here
        if (s1 == null || s1.length() == 0) {
            return 0;
        }
        
        int[] parents = new int[26];
        int ans = 0;
        
        for (int i = 0; i < 26; i++) {
            parents[i] = i;
        }
        
        for (int i = 0; i < s1.length(); i++) {
            int n1 = s1.charAt(i) - 'a';
            int n2 = s2.charAt(i) - 'a';
            
            int p1 = find(n1, parents);
            int p2 = find(n2, parents);
            
            if (p1 != p2) {
                ans++;
                parents[p1] = p2;
            }
        }
        
        return ans;
    }
    
    private int find(int node, int[] parents) {
        int root = node;
        
        while (parents[root] != root) {
            root = parents[root];
        }
        
        while (root != node) {
            int parent = parents[node];
            parents[node] = root;
            node = parent;
        }
        
        return root;
    }
}

Lintcode 793. Intersection of Arrays

Give a number of arrays, find their intersection, and output their intersection size.

Example

Example 1:

 Input:  [[1,2,3],[3,4,5],[3,9,10]]
 Output:  1
 
 Explanation:
 Only '3' in all three array.

Example 2:

 Input: [[1,2,3,4],[1,2,5,6,7][9,10,1,5,2,3]]
 Output:  2
 
 Explanation:
 The set is [1,2].

Notice

• The total number of all array elements is not more than 500000.
• There are no duplicated elements in each array.

Code (Java):

public class Solution {
    /**
     * @param arrs: the arrays
     * @return: the number of the intersection of the arrays
     */
    public int intersectionOfArrays(int[][] arrs) {
        // write your code here
        if (arrs == null || arrs.length == 0) {
            return 0;
        }
        
        return intersectionOfArraysHelper(0, arrs.length - 1, arrs).length;
    }
    
    private int[] intersectionOfArraysHelper(int start, int end, int[][] arrs) {
        if (start == end) {
            return arrs[start];
        }
        
        int mid = start + (end - start) / 2;
        int[] left = intersectionOfArraysHelper(start, mid, arrs);
        int[] right = intersectionOfArraysHelper(mid + 1, end, arrs);
        
        return intersectionOfTwoArray(left, right);
    }
    
    private int[] intersectionOfTwoArray(int[] left, int[] right) {
        Arrays.sort(left);
        Arrays.sort(right);
        
        int i = 0;
        int j = 0;
        
        List<Integer> ans = new ArrayList<>();
        while (i < left.length && j < right.length) {
            if (left[i] == right[j]) {
                ans.add(left[i]);
                i++;
                j++;
            } else if (left[i] < right[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        int[] ans2 = new int[ans.size()];
        for (i = 0; i < ans2.length; i++) {
            ans2[i] = ans.get(i);
        }
        
        return ans2;
    }
}

Lintcode 550. Top K Frequent Words II

ind top k frequent words in realtime data stream.

Implement three methods for Topk Class:

1. TopK(k). The constructor.
2. add(word). Add a new word.
3. topk(). Get the current top k frequent words.

Example

Example 1:

Input：
TopK(2)
add("lint")
add("code")
add("code")
topk()
Output：["code", "lint"]
Explanation：
"code" appears twice and "lint" appears once, they are the two most frequent words.

Example 2:

Input：
TopK(1)
add("aa")
add("ab")
topk()
Output：["aa"]
Explanation：
"aa" and "ab" appear once , but aa's dictionary order is less than ab's.

Notice

If two words have the same frequency, rank them by dictionary order.

Analysis:
The main difference between the top k frequent word I is now we keep adding new words. So the count of each word is changing dynamically. 

It means in the minHeap, we need to support an update operation update(E e), which is a O(N) operation. Why? It first needs to find the node. Since there is no order in priority queue, the search operation takes O(N) time. Once we find the element, we need to first remove it (O(logn)) and insert a new node O(logn). 

So do we have some other data structure providing similar operations but the search can be done in O(log(N)) time? Yes, we can use a TreeSet/TreeMap which is literally a red-black tree. Since it's a ordered tree, the search now takes O(log n) time and update takes O(logn) as well. 

Code (Java):

public class TopK {
    private Map<String, Integer> wordCountMap;
    private TreeSet<String> topKTreeSet;
    private int k;
    
    /*
    * @param k: An integer
    */public TopK(int k) {
        // do intialization if necessary
        this.k = k;
        this.wordCountMap = new HashMap<>();
        this.topKTreeSet = new TreeSet<>(new MyTreeSetComparator());
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        int count = 0;
        if (wordCountMap.containsKey(word)) {
            count = wordCountMap.get(word);
            if (topKTreeSet.contains(word)) {
                topKTreeSet.remove(word);
            }
        }
        
        count += 1;
        wordCountMap.put(word, count);
        topKTreeSet.add(word); // count has been bumped up by 1
        
        if (topKTreeSet.size() > k) {
            topKTreeSet.pollFirst();
        }
    }

    /*
     * @return: the current top k frequent words.
     */
    public List<String> topk() {
        // write your code here
        List<String> ans = new ArrayList<>(k);
        Iterator<String> iter = topKTreeSet.iterator();
        while (iter.hasNext()) {
            String word = iter.next();
            ans.add(word);
        }
        
        Collections.reverse(ans);
        
        return ans;
    }
    
    private class MyTreeSetComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            int freqA = wordCountMap.get(a);
            int freqB = wordCountMap.get(b);
            
            if (freqA != freqB) {
                return freqA - freqB;
            }
            
            return b.compareTo(a);
        }
    }
}