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