Leetcode 544. Output Contest Matches

During the NBA playoffs, we always arrange the rather strong team to play with the rather weak team, like make the rank 1 team play with the rank nth team, which is a good strategy to make the contest more interesting. Now, you're given n teams, you need to output their final contest matches in the form of a string.

The n teams are given in the form of positive integers from 1 to n, which represents their initial rank. (Rank 1 is the strongest team and Rank n is the weakest team.) We'll use parentheses('(', ')') and commas(',') to represent the contest team pairing - parentheses('(' , ')') for pairing and commas(',') for partition. During the pairing process in each round, you always need to follow the strategy of making the rather strong one pair with the rather weak one.

Example 1:

Input: 2
Output: (1,2)
Explanation: 
Initially, we have the team 1 and the team 2, placed like: 1,2.
Then we pair the team (1,2) together with '(', ')' and ',', which is the final answer.

Example 2:

Input: 4
Output: ((1,4),(2,3))
Explanation: 
In the first round, we pair the team 1 and 4, the team 2 and 3 together, as we need to make the strong team and weak team together.
And we got (1,4),(2,3).
In the second round, the winners of (1,4) and (2,3) need to play again to generate the final winner, so you need to add the paratheses outside them.
And we got the final answer ((1,4),(2,3)).

Example 3:

Input: 8
Output: (((1,8),(4,5)),((2,7),(3,6)))
Explanation: 
First round: (1,8),(2,7),(3,6),(4,5)
Second round: ((1,8),(4,5)),((2,7),(3,6))
Third round: (((1,8),(4,5)),((2,7),(3,6)))
Since the third round will generate the final winner, you need to output the answer (((1,8),(4,5)),((2,7),(3,6))).

Note:

1. The n is in range [2, 212].
2. We ensure that the input n can be converted into the form 2k, where k is a positive integer.

Code (Java):

class Solution {
    public String findContestMatch(int n) {
        List<String> prev = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            prev.add(i + "");
        }
        
        while (n > 1) {
            List<String> curr = new ArrayList<>();
            for (int i = 0; i < prev.size() / 2; i++) {
                String a = prev.get(i);
                String b = prev.get(prev.size() - i - 1);
                String s = '(' + a + ',' + b + ')';
                curr.add(s);
            }
            prev = curr;
            n /= 2;
        }
        
        return prev.get(0);
    }
}

Leetcode 541. Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

1. The string consists of lower English letters only.
2. Length of the given string and k will in the range [1, 10000]

Code (Java):

class Solution {
    public String reverseStr(String s, int k) {
        if (k <= 1) {
            return s;
        }

        char[] charArr = s.toCharArray();
        int start = 0;
        int end = 0;

        while (start < charArr.length) {
            end = Math.min(start + k - 1, charArr.length - 1);
            reverse(charArr, start, end);

            start += k * 2;
        }

        return new String(charArr);
    }

    private void reverse(char[] charArr, int start, int end) {
        while (start < end) {
            char temp = charArr[start];
            charArr[start] = charArr[end];
            charArr[end] = temp;

            start++;
            end--;
        }
    }
}

Leetcode 539. Minimum Time Difference

Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

1. The number of time points in the given list is at least 2 and won't exceed 20000.
2. The input time is legal and ranges from 00:00 to 23:59.

Code (Java):

class Solution {
    public int findMinDifference(List<String> timePoints) {
        boolean[] minutes = new boolean[1440];

        for (String time : timePoints) {
            int minute = convertToMinutes(time);
            if (minutes[minute]) {
                return 0;
            }

            minutes[minute] = true;
        }

        // iterate through the minutes and find the minimum findMinDifference
        //
        int prev = -1;
        int first = -1;
        int curr = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < minutes.length; i++) {
            if (prev == -1) {
                if (minutes[i] == true) {
                    prev = i;
                    first = i;
                }
                continue;
            }

            if (minutes[i]) {
                curr = i;
                int diff = i - prev;
                diff = Math.min(diff, 1440 - diff);
                min = Math.min(min, diff);
                prev = i;
            }
        }
        int diff = curr - first;
        min = Math.min(min, Math.min(diff, 1440 - diff));

        return min;
    }

    private int convertToMinutes(String s) {
        String[] tokens = s.split("[:]");
        int hour = Integer.parseInt(tokens[0]);
        int minute = Integer.parseInt(tokens[1]);

        return hour * 60 + minute;
    }
}

Leetcode 537. Complex Number Multiplication

Given two strings representing two complex numbers.

You need to return a string representing their multiplication. Note i2 = -1 according to the definition.

Example 1:

Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Example 2:

Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

Note:

1. The input strings will not have extra blank.
2. The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

Code (Java):

class Solution {
    public String complexNumberMultiply(String a, String b) {
        // parse the r and i
        //
        String delim = "[+]";
        String[] tokensA = a.split(delim);
        String[] tokensB = b.split(delim);

        // get real part
        //
        int r1 = getInteger(tokensA[0]);
        int r2 = getInteger(tokensB[0]);

        // get imiminary part
        //
        int i1 = getInteger(tokensA[1].substring(0, tokensA[1].length() - 1));
        int i2 = getInteger(tokensB[1].substring(0, tokensB[1].length() - 1));

        // compose the result
        //
        int r3 = r1 * r2 - i1 * i2;
        int i3 = r1 * i2 + r2 * i1;

        return r3 + "+" + i3 + "i";
    }

    private int getInteger(String s) {
        boolean isNeg = false;
        int i = 0;
        if (s.charAt(0) == '-') {
            isNeg = true;
            i++;
        }

        int result = 0;
        while (i < s.length()) {
            int digit = Character.getNumericValue(s.charAt(i));
            result = result * 10 + digit;
            i++;
        }

        if (isNeg) {
            result = -result;
        }

        return result;
    }
}

Leetcode 522. Longest Uncommon Subsequence II

Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.

Example 1:

Input: "aba", "cdc", "eae"
Output: 3

Note:

1. All the given strings' lengths will not exceed 10.
2. The length of the given list will be in the range of [2, 50].

Code (Java):

class Solution {
    public int findLUSlength(String[] strs) {
        if (strs == null || strs.length <= 1) {
            return -1;
        }

        // sort in reverse reverseOrder
        //
        Arrays.sort(strs, new MyComparator());

        for (int i = 0; i < strs.length; i++) {
            if ((i != strs.length - 1) && strs[i].equals(strs[i + 1])) {
                continue;
            }

            if (!isSubsequence(i, strs)) {
                return strs[i].length();
            }
        }

        return -1;
    }

    private boolean isSubsequence(int curr, String[] strs) {
        String currStr = strs[curr];

        for (int i = 0; i < curr; i++) {
            if (isSubsequenceHelper(currStr, strs[i])) {
                return true;
            }
        }

        return false;
    }

    private boolean isSubsequenceHelper(String a, String b) {
        int i = 0;
        int j = 0;
        while (i < a.length() && j < b.length()) {
            if (a.charAt(i) == b.charAt(j)) {
                i++;
                j++;
            } else {
                j++;
            }
        }

        return i == a.length();
    }
}

 class MyComparator implements Comparator<String> {
    public int compare(String a, String b) {
        if (a.length() < b.length()) {
            return 1;
        } else if (a.length() > b.length()) {
            return -1;
        }
        
        // length is equal
        //
        if (a.equals(b)) {
            return 0;
        }
        
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) == b.charAt(i)) {
                continue;
            }
            
            return b.charAt(i) - a.charAt(i); 
        }
        
        return 0;
    }
}

Leetcode 520. Detect Capital

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

1. All letters in this word are capitals, like "USA".
2. All letters in this word are not capitals, like "leetcode".
3. Only the first letter in this word is capital if it has more than one letter, like "Google".

Otherwise, we define that this word doesn't use capitals in a right way.

Example 1:

Input: "USA"
Output: True

Example 2:

Input: "FlaG"
Output: False

Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.

Code (Java):

class Solution {
    public boolean detectCapitalUse(String word) {
        if (word == null || word.isEmpty()) {
            return true;
        }

        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c >= 'A' && c <= 'Z') {
                count++;
            }
        }

        if (count == 0 || count == word.length()) {
            return true;
        }

        if (count == 1 && word.charAt(0) >= 'A' && word.charAt(0) <= 'Z') {
            return true;
        }

        return false;
    }
}

Leetcode 468. Validate IP Address

Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.

IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots ("."), e.g.,172.16.254.1;

Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.

IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (":"). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).

However, we don't replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.

Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.

Note: You may assume there is no extra space or special characters in the input string.

Example 1:

Input: "172.16.254.1"

Output: "IPv4"

Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"

Output: "IPv6"

Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

Input: "256.256.256.256"

Output: "Neither"

Explanation: This is neither a IPv4 address nor a IPv6 address.

Code (Java):

class Solution {
    public String validIPAddress(String IP) {
        if (IP == null || IP.length() == 0) {
            return "Neither";
        }

        if (IP.contains(".")) {
            boolean valid = validateIPv4(IP);
            if (valid) {
                return "IPv4";
            }
        } else if (IP.contains(":")) {
            boolean valid = validateIPv6(IP);
            if (valid) {
                return "IPv6";
            }
        }

        return "Neither";
    }

    private boolean validateIPv4(String s) {
        String[] tokens = s.split("[.]");
        if (tokens.length != 4) {
            return false;
        }
        
        if (s.charAt(0) == '.' || s.charAt(s.length() - 1) == '.') {
            return false;
        }

        for (String token : tokens) {
            if (!validateIpv4Helper(token)) {
                return false;
            }
        }

        return true;
    }

    private boolean validateIpv4Helper(String s) {
        if (s == null || s.length() == 0 || s.length() > 3) {
            return false;
        }
        
        if (s.length() > 1 && s.charAt(0) == '0') {
            return false;
        }

        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c < '0' || c > '9') {
                return false;
            }

            int digit = (int)(c - '0');
            num = num * 10 + digit;
        }

        if (num < 0 || num > 255) {
            return false;
        }

        return true;
    }

    private boolean validateIPv6(String s) {
        if (s.charAt(0) == ':' || s.charAt(s.length() - 1) == ':') {
            return false;
        }
        
        String[] tokens = s.split("[:]");
        if (tokens.length != 8) {
            return false;
        }

        for (String token : tokens) {
            if (!validateIpv6Helper(token)) {
                return false;
            }
        }

        return true;
    }

    private boolean validateIpv6Helper(String s) {
        if (s == null || s.length() == 0 || s.length() > 4) {
            return false;
        }

        s = s.toLowerCase();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                if (c < '0' || c > '9') {
                    return false;
                }
            } else {
                if (c < 'a' || c > 'f') {
                    return false;
                }
            }
        }

        return true;
    }
}

Leetcode 536. Construct Binary Tree from String

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example:

Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5   

Note:

1. There will only be '(', ')', '-' and '0' ~ '9' in the input string.
2. An empty tree is represented by "" instead of "()"

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int start = 0;
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        return str2treeHelper(s);
    }

    private TreeNode str2treeHelper(String s) {
        if (start >= s.length()) {
            return null;
        }

        // parse int
        //
        boolean neg = false;
        if (s.charAt(start) == '-') {
            neg = true;
            start++;
        }
        int num = 0;
        while (start < s.length() && Character.isDigit(s.charAt(start))) {
            int digit = Character.getNumericValue(s.charAt(start));
            num = num * 10 + digit;
            start++;
        }

        if (neg) {
            num = -num;
        }

        TreeNode root = new TreeNode(num);

        if (start >= s.length()) {
            return root;
        }

        // go to left child
        //
        if (start < s.length() && s.charAt(start) == '(') {
            start++;
            root.left = str2treeHelper(s);
        }

        if (start < s.length() && s.charAt(start) == ')') {
            start++;
            return root;
        }

        // go to the right child
        //
        if (start < s.length() && s.charAt(start) == '(') {
            start++;
            root.right = str2treeHelper(s);
        }

        if (start < s.length() && s.charAt(start) == ')') {
            start++;
            return root;
        }

        return root;
    }
}

Leetcode 443. String Compression

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

1. All characters have an ASCII value in [35, 126].
2. 1 <= len(chars) <= 1000.

Code (Java):

class Solution {
    public int compress(char[] chars) {
        if (chars == null || chars.length == 0) {
            return 0;
        }
        
        int newPos = 0;
        int count = 1;
        for (int i = 0; i < chars.length; i++) {
            count = 1;
            while (i < chars.length && i != chars.length - 1 && (chars[i] == chars[i + 1])) {
                count++;
                i++;
            }

            int numChars = getNumberofChars(count);
            newPos = copyArray(chars, newPos, chars[i], count, numChars);
        }
        
        return newPos;
    }

    private int copyArray(char[] chars, int pos, char c, int count, int numChars) {
        chars[pos] = c;
        pos++;

        if (count > 1) {
            int end = pos + numChars - 1;
            while (count > 0) {
                int digit = count % 10;
                chars[end] = (char)(digit + '0');
                end--;

                count /= 10;
            }

            pos += numChars;
        }

        return pos;
    }

    private int getNumberofChars(int num) {
        int ans = 0;
        if (num < 10) {
            ans = 1;
        } else if (num < 100) {
            ans = 2;
        } else if (num < 1000) {
            ans = 3;
        } else {
            ans = 4;
        }

        return ans;
    }
}

Leetcode 408. Valid Word Abbreviation

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.

A string such as "word" contains only the following valid abbreviations:

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Notice that only the above abbreviations are valid abbreviations of the string "word". Any other string is not a valid abbreviation of "word".

Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.

Example 1:

Given s = "internationalization", abbr = "i12iz4n":

Return true.

Example 2:

Given s = "apple", abbr = "a2e":

Return false.

Code (Java):

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        if (word.isEmpty()) {
            return abbr.isEmpty();
        }

        int pWord = 0;
        int pAbbr = 0;

        while (pWord < word.length() && pAbbr < abbr.length()) {
            if (!Character.isDigit(abbr.charAt(pAbbr))) {
                if (word.charAt(pWord) == abbr.charAt(pAbbr)) {
                    pWord++;
                    pAbbr++;
                } else {
                    return false;
                }
            } else {           
                // edge case: leading zero
                //
                if (abbr.charAt(pAbbr) == '0') {
                    return false;
                }
                
                int num = 0;
                while (pAbbr < abbr.length() && Character.isDigit(abbr.charAt(pAbbr))) {
                    int digit = Character.getNumericValue(abbr.charAt(pAbbr));
                    num = num * 10 + digit;
                    pAbbr++;
                }

                pWord += num;
            }
        }

        return pWord == word.length() && pAbbr == abbr.length();
    }
}

Leetcode 387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

Code (Java):

class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }

        int[] counts = new int[26];

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            counts[c - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (counts[c - 'a'] == 1) {
                return i;
            }
        }

        return -1;
    }
}

Leetcode 727. Minimum Window Subsequence

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.

If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1:

Input: 
S = "abcdebdde", T = "bde"
Output: "bcde"
Explanation: 
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of T in the window must occur in order.

Note:

• All the strings in the input will only contain lowercase letters.
• The length of S will be in the range [1, 20000].
• The length of T will be in the range [1, 100]

Analysis:
This is a two-sequence DP problem. We define dp[S.length() + 1][T.length() + 1], where dp[i][j] means the START POSITION of the minimum windows subsequnce for the first i charactgers from S and first j characters from T.

Code (Java):

class Solution {
    public String minWindow(String S, String T) {
        if (S == null || S.length() == 0 || T == null || T.length() == 0) {
            return "";
        }
        
        int[][] dp = new int[S.length() + 1][T.length() + 1];
        for (int i = 1; i <= T.length(); i++) {
            dp[0][i] = -1;
        }
        
        for (int i = 1; i <= S.length(); i++) {
            dp[i][0] = i;
        }
        
        int minLen = Integer.MAX_VALUE;
        int startPos = -1;
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= T.length(); j++) {
                dp[i][j] = -1;
                
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            
            if (dp[i][T.length()] != -1) {
                int len = i - dp[i][T.length()];
                if (len < minLen) {
                    startPos = dp[i][T.length()];
                    minLen = len;
                }
            }
        }
        
        return startPos == -1? "" : S.substring(startPos, startPos + minLen);
    }
}

Leetcode 486. Predict the Winner

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return False.

Example 2:

Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Note:

1. 1 <= length of the array <= 20.
2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
3. If the scores of both players are equal, then player 1 is still the winner.

Solution 1: Backtracking + Memo:
Since each player wanna get the optimal results, we can maintain the score each player can get for choosing a number, and only return the best score. 

Code (Java):

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        
        return PredictTheWinnerHelper(nums, 0, nums.length - 1, dp) >= 0;
    }
    
    private int PredictTheWinnerHelper(int[] nums, int start, int end, int[][] dp) {
        if (start == end) {
            return nums[start];
        }
        
        if (dp[start][end] != 0) {
            return dp[start][end];
        }
        
        int max =  Math.max(nums[start] - PredictTheWinnerHelper(nums, start + 1, end, dp), 
                            nums[end] - PredictTheWinnerHelper(nums, start, end - 1, dp));
        
        
        dp[start][end] = max;
        
        return max;
    }
}

Solution 2: Top-Down DP:

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            dp[i][i] = nums[i];
        }
        
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < nums.length; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], 
                                    nums[j] - dp[i][j - 1]);
            }
        }
        
        return dp[0][nums.length - 1] >= 0;
    }
    
}

Leetcode 467. Unique Substrings in Wraparound String

Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

Input: "a"
Output: 1

Explanation: Only the substring "a" of string "a" is in the string  s.

Example 2:

Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

Code (Java):

class Solution {
    public int findSubstringInWraproundString(String p) {
        if (p == null || p.length() == 0) {
            return 0;
        }
        
        int[] count = new int[26];
        int ans = 0;
        int maxLen = 1;
        count[p.charAt(0) - 'a'] = 1;
        
        for (int i = 1; i < p.length(); i++) {
            char curr = p.charAt(i);
            char prev = p.charAt(i - 1);
            
            if (Character.getNumericValue(curr) == Character.getNumericValue(prev) + 1 
                || (prev == 'z' && curr == 'a')) {
                maxLen++;
            } else {
                maxLen = 1;
            }
            
            count[curr - 'a'] = Math.max(count[curr - 'a'], maxLen);
        }
        
        for (int i = 0; i < count.length; i++) {
            ans += count[i];
        }
                
        return ans;
    }
}

Leetcode 446. Arithmetic Slices II - Subsequence

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.

A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

Example:

Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

Analysis:
It's a DP problem. Since for each element A[i] when it's part of a arithmetic sequence, its difference can be different. For example, [2, 4, 6] and [2, 6, 10]. For number 2 and 6, they can be in different arithmetic sequences. 

So for each dp[i], we need to maintain a hashmap, the key is the diff, and value is the number of pairs with this diff. 

Then for each pair [i, j] in the array A, we check if we have seen the diff before. If yes, we add a pair and calculate the number of subsequences added in.

Code (Java):

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if (A == null || A.length < 3) {
            return 0;
        }
        
        Map<Integer, Integer>[] dp = (Map<Integer, Integer>[])new HashMap<?,?>[A.length];
        
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new HashMap<>();
        }
        
        int ans = 0;
        
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                long diff = (long)A[j] - (long)A[i];
                if (diff > Integer.MAX_VALUE || diff < Integer.MIN_VALUE) {
                    continue;
                }
                
                int delta = (int) diff;
                int vali = dp[i].getOrDefault(delta, 0);
                ans += vali;
                
                vali += 1;
                int valj = dp[j].getOrDefault(delta, 0);
                dp[j].put(delta, vali + valj);
            }
        }
        
        return ans;
    }
}

Leetcode 418. Sentence Screen Fitting

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

1. A word cannot be split into two lines.
2. The order of words in the sentence must remain unchanged.
3. Two consecutive words in a line must be separated by a single space.
4. Total words in the sentence won't exceed 100.
5. Length of each word is greater than 0 and won't exceed 10.
6. 1 ≤ rows, cols ≤ 20,000.

Example 1:

Input:
rows = 2, cols = 8, sentence = ["hello", "world"]

Output: 
1

Explanation:
hello---
world---

The character '-' signifies an empty space on the screen.

Example 2:

Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]

Output: 
2

Explanation:
a-bcd- 
e-a---
bcd-e-

The character '-' signifies an empty space on the screen.

Example 3:

Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]

Output: 
1

Explanation:
I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

Code (Java):

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String str = "";
        
        for (String word : sentence) {
            str += word + " ";
        }
        
        int len = str.length();
        
        int start = 0;
        for (int i = 0; i < rows; i++) {
            start += cols;
            
            if (str.charAt(start % len) == ' ') {
                start++;
                continue;
            }
            
            while ((start % len - 1 >= 0) && str.charAt(start % len - 1) != ' ') {
                start--;
            }
        }
        
        return start / len;
    }
}