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;
    }
}

Lintcode 1397. Digital Coverage

Description

Given some intervals, ask how many are covered most, if there are multiple, output the smallest number.

• the number of the interval is not more than 10^5.
• the left and right endpoints of the interval are greater than 0 not more than 10^5.

Have you met this question in a real interview?  

Example

Example 1:

 Input:intervals = [(1,7),(2,8)]
 Output:2
Explanation:2 is covered 2 times, and is the number of 2 times the smallest number.

Example 2:

Input:intervals = [(1,3),(2,3),(3,4)]
Output:3 

Explanation:3 is covered 3 times. 

Solution 1:

Split the interval into events and sort by start time. Time complexity O(nlogn)

Code (Java):

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: The intervals
     * @return: The answer
     */
    public int digitalCoverage(List<Interval> intervals) {
        // Write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
        
        List<Event> events = new ArrayList<>();
        for (Interval interval : intervals) {
            events.add(new Event(interval.start, 0));
            events.add(new Event(interval.end, 1));
        }
        
        Collections.sort(events, new MyEventComparator());
        
        int count = 0;
        int ans = 0;
        int maxCount = 0;
        
        for (Event event : events) {
            if (event.flag == 0) {
                count++;
            } else {
                count--;
            }
            
            if (count > maxCount) {
                maxCount = count;
                ans = event.time;
            }
        }
        
        return ans;
    }
}

class Event {
    int time;
    int flag; // 0 start, 1 end
    
    public Event(int time, int flag) {
        this.time = time;
        this.flag = flag;
    }
}

class MyEventComparator implements Comparator<Event> {
    @Override
    public int compare(Event a, Event b) {
        if (a.time != b.time) {
            return a.time - b.time;
        }
        
        return a.flag - b.flag;
    }
}

Solution 2: prefix sum

Allocate an array with size of data range (10^5 for this problem). for each interval, if it's start, count + 1, otherwise count - 1. In the end, we sum up the counts and get the max number.

Time complexity is O(data range)

Code (Java):

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: The intervals
     * @return: The answer
     */
    public int digitalCoverage(List<Interval> intervals) {
        // Write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
        
        int[] counts = new int[1000001];
        
        for (Interval interval : intervals) {
            counts[interval.start] += 1;
            counts[interval.end + 1] -= 1;
        }
        
        int maxCount = 0;
        int count = 0;
        int ans = -1;
        
        for (int i = 0; i < counts.length; i++) {
            count += counts[i];
            if (count > maxCount) {
                maxCount = count;
                ans = i;
            }
        }
        
        return ans;
    }
}

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 1257. Evaluate Division

Description

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

• The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Have you met this question in a real interview?  

Example

Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, 
vector<double>& values, 
vector<pair<string, string>> queries , 
where equations.size() == values.size(), and the values are positive. 
This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0], 

queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

Solution:

Graph + DFS

Code (Java):

public class Solution {
    /**
     * @param equations: 
     * @param values: 
     * @param queries: 
     * @return: return a double type array
     */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // write your code here
        double[] ans = new double[queries.size()];
        
        if (equations == null || equations.size() == 0 || values == null|| values.length == 0) {
            return ans;
        }
        
        // build the graph
        Map<String, List<Node>> adjList = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            double value = values[i];
            String n1 = equation.get(0);
            String n2 = equation.get(1);
            
            // n1->n2
            List<Node> neighbors = adjList.getOrDefault(n1, new ArrayList<>());
            neighbors.add(new Node(n2, value));
            adjList.put(n1, neighbors);
            
            // n2->n1
            List<Node> neighbors2 = adjList.getOrDefault(n2, new ArrayList<>());
            neighbors2.add(new Node(n1, 1.0 / value));
            adjList.put(n2, neighbors2);
        }
        
        // dfs to find the answer
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String n1 = query.get(0);
            String n2 = query.get(1);
            
            if (!adjList.containsKey(n1) || !adjList.containsKey(n2)) {
                ans[i] = -1.0;
            } else if (n1.equals(n2)) {
                ans[i] = 1.0;
            } else {
                Set<String> visited = new HashSet<>();
                RetVal retval = dfs(n1, n2, adjList, 1.0, visited);
                if (retval.found) {
                    ans[i] = retval.val;
                } else {
                    ans[i]= -1.0;
                }
            }
        }
        
        return ans;
    }
    
    private RetVal dfs(String start, String end, Map<String, List<Node>> adjList, double val, Set<String> visited) {
        RetVal retval = new RetVal(false, -1.0);
        visited.add(start);
        
        if (start.equals(end)) {
            return new RetVal(true, val);
        }
        
        List<Node> neighbors = adjList.get(start);
        
        for (Node neighbor: neighbors) {
            if (visited.contains(neighbor.label)) {
                continue;
            }
            
            retval = dfs(neighbor.label, end, adjList, val * neighbor.val, visited);
            
            if (retval.found) {
                return retval;
            }
        }
        
        visited.remove(start);
        return retval;
    }
}

class Node {
    String label;
    double val;
    
    public Node (String label, double val) {
        this.label = label;
        this.val = val;
    }
}

class RetVal {
    boolean found;
    double val;
    
    public RetVal (boolean found, double val) {
        this.found = found;
        this.val = val;
    }
}