[Leetcode] 2296. Design a Text Editor

2296. Design a Text Editor

Design a text editor with a cursor that can do the following:

Add text to where the cursor is.

Delete text from where the cursor is (simulating the backspace key).

Move the cursor either left or right.

When deleting text, only characters to the left of the cursor will be deleted. The cursor will also remain within the actual text and cannot be moved beyond it. More formally, we have that 0 <= cursor.position <= currentText.length always holds.

Implement the TextEditor class:

TextEditor() Initializes the object with empty text.

void addText(string text) Appends text to where the cursor is. The cursor ends to the right of text.

int deleteText(int k) Deletes k characters to the left of the cursor. Returns the number of characters actually deleted.

string cursorLeft(int k) Moves the cursor to the left k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.

string cursorRight(int k) Moves the cursor to the right k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.

Constraints:

1 <= text.length, k <= 40

text consists of lowercase English letters.

At most 2 * 10^4 calls in total will be made to addText, deleteText, cursorLeft and cursorRight.

Analysis:

This question is labeled as hard in Leetcode, but the logic is quick straightforward. The only problem is the efficiency. 

If we use a string and an index for the cursor position, then we will see TLE or MLE.

One neat method is to use two stacks, one is the left stack and the other is right stack. 

For add, we just push the new string into left stack;

for delete, we just pop up the chars from the left stack;

for leftMove, we just pop out k or less (if less than k elements remains) chars from left stack, and push in right stack; then return 10 or less(if less than 10 elements remains) from the left stack;

for rightMore we just need to do the reversed operation as that for the leftMove.

See the code below

class TextEditor {
public:
    TextEditor() {
    }
    
    void addText(string text) {
        for(auto &a : text) lt.push(a);
    }
    
    int deleteText(int k) {
        int res = 0;
        while (lt.size() && k > 0) {
            lt.pop();
            ++res;
            --k;
        }
        // cout << "delet" << endl;
        return res;
    }
    
    string cursorLeft(int k) {
        while(lt.size() && k > 0) {
            auto t = lt.top();
            lt.pop();
            rt.push(t);
            --k;
        }
        return f(lt, 10);
    }
    
    string cursorRight(int k) {
         while(rt.size() && k > 0) {
            auto t = rt.top();
            rt.pop();
            lt.push(t);
            --k;
        }
        return f(lt, 10);
    }
private:
    stack<int> lt, rt;
    string f(stack<int> &sk, int k) {
        string res;
        while(sk.size() && k > 0) {
            res.push_back(sk.top());
            sk.pop();
            --k;
        }
        reverse(res.begin(), res.end());
        for(auto &a : res) sk.push(a);
        return res;
    }
};

/**
 * Your TextEditor object will be instantiated and called as such:
 * TextEditor* obj = new TextEditor();
 * obj->addText(text);
 * int param_2 = obj->deleteText(k);
 * string param_3 = obj->cursorLeft(k);
 * string param_4 = obj->cursorRight(k);
 */

[Leetcode] 2293. Min Max Game

2293. Min Max Game

You are given a 0-indexed integer array nums whose length is a power of 2.

Apply the following algorithm on nums:

Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.

For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).

For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).

Replace the array nums with newNums.

Repeat the entire process starting from step 1.

Return the last number that remains in nums after applying the algorithm.

Constraints:

1 <= nums.length <= 1024

1 <= nums[i] <= 10^9

nums.length is a power of 2.

Analysis

This question can be resolved by the classic Divide and Conquer algorithm.

The only extra thing is we need a flag to indicate whether it is the first half or the second half.

when flag == 0, we choose the min;

when flag == 1, we choose the max.

See the code below:

class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        return f(nums, 0, nums.size(), 0);
    }
private:
    int f(vector<int>&ns, int left, int right, int flag) {
        if(left+1 == right) return ns[left];
        int mid = left + (right - left)/2;
        int x = f(ns, left, mid, 0), y = f(ns, mid, right, 1);
        return flag ? max(x, y) : min(x, y);
    }
};

[Leetcode] 813. Largest Sum of Averages

813. Largest Sum of Averages

You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in nums, and that the score is not necessarily an integer.

Return the maximum score you can achieve of all the possible partitions. Answers within 10-6 of the actual answer will be accepted.

Constraints:

1 <= nums.length <= 100

1 <= nums[i] <= 10^4

1 <= k <= nums.length

Analysis:

This question asks for the an maximum value, so we usually can consider dp first.

As it is known, the key for dp is to find the transition formula. Or find the key parameters than describe an "intermediate state" completely.

The intermediate state here represents a similar question but with a smaller size.

For this question, we can try to define the state as dp[i][k], where i is the index of the elements and k is the number of subarrays.

The meaning of dp[i][k] is the maximum of average sum ending with the ith element with at most k subarrays.

Then the next step is to derive the formula to calculate the value of dp[i][k] using the previous dp with smaller values of i and k.

dp[i][k] = max(dp[x][k-1] + sum(num[x+1] to nums[i])/(i-x)), where x from 0 to i-1.

With the meaning of dp[x][k-1], the above formula is not hard to understand:

The right-hand side (rhs) enumerates all the possible ways to calculate dp[i][k], so we just need to pick up the maximum of it.

In the implementation, the boundary conditions are tricky. The thumb rule is to make sure the dp[i][k] is valid. For example, dp[i>0][0] is not valid, since there is no such case that we have non-zero elements in 0 subarray.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        // dp[i][j]: the max, ending at i, up to j subarray;
        // dp[i][j] = max(dp[d][j-1] + sum(nums[d+1], ..., nums[i])/(i-d))
        // where d from j-1 to i-1.
        double res = 0;
        int n = nums.size();
        vector<double> sums(n+1, 0);
        for(int i=0; i<n; ++i) sums[i+1] = sums[i] + nums[i];
        vector<vector<double>> dp(n+1, vector<double>(k+1, 0));
        for(int i=1; i<=n; ++i) {
            for(int j=min(i, k); j>=1; --j) {
                for(int d=max(j-1, 1); d<=i; ++d) {
                    double v = (j==1&&d>1) ? 0 : (dp[d-1][j-1] + (sums[i]-sums[d-1])/(i-d+1));
                    dp[i][j] = max(dp[i][j], v);
                }
            }
        }
        return dp[n][k];
    }
};

If do not like the boundary conditions of the above dp solution, we can try dfs + memoization.

We can start from the beginning of the array, and stop to make a subarray at any possible places.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<double>> memo(n, vector<double>(k, -1));
        return dfs(nums, 0, k-1, memo);
    }
private:
    double dfs(vector<int>& ns, int id, int k, vector<vector<double>>& memo) {
        // invalid ending since we cannot have more than k subarrays
        if(k<0 && id<ns.size()) return -2;
        if(id==ns.size()) return 0;
        if(memo[id][k] != -1) return memo[id][k];
        double t = 0, sum = 0;
        for(int i=id; i<ns.size(); ++i) {
            sum += ns[i];
            double v = dfs(ns, i+1, k-1, memo);
            if(v>-2) t = max(t, sum/(i-id+1) + v);
        }
        return memo[id][k] = t;
    }
};

  

[Leetcode] 2104. Sum of Subarray Ranges

2104. Sum of Subarray Ranges

You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Constraints:

1 <= nums.length <= 1000

-10^9 <= nums[i] <= 10^9

 

Follow-up: Could you find a solution with O(n) time complexity? 

Analysis:

First of all, we can use a two-layer for loop to solve this problem, since the maximum length is 10^3, so O(N^2) is acceptable for the online OJ.

For any array with N elements, there are N*(N+1)/2 sub-arrays. So we just need to get the min and max of each sub-array, and sum the diffs together.

See the code below:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long res = 0, n = nums.size();
        for(int i=0; i<n; ++i) {
            int mx = nums[i], mi = mx;
            for(int j=i+1; j<n; ++j) {
                mx = max(nums[j], mx);
                mi = min(nums[j], mi);
                res += (long)mx - (long)mi;
            }
        }
        return res;
    }
};

As asked in the follow up, can we do better?

(Please be noted: the following logic is quite non-intuitive, and requires at least 10 min to read.)

The answer is yes. For example, with a stack, the time complexity can be decreased to O(N).

Think about one classical question about stack: In an integer array with size of N, for each element, what is the first element larger than it?

 One observation is that: if we maintain a monotonically increasing stack, then we can derive many useful information. For example, we can derive the answers to the above question for every elements in a time complexity of O(N), or just in one scan for every element. 

At the same time, we can get the number of the elements larger than every element on its right side continuously!

For example, say we have one array [6, 9, 3, 5, 10, 1, 4, 7], and we will use a stack to scan through the array from left to right.

One trick here is to use the index instead of value (recording index is obvious better than value with an array, since once we know the index, we know the value as well; but not the reverse)

At step 1, we have [0];

            2,                [0, 1]

At step 3, the index is 2 and the value is 3, and 3 < arr[1] == 9 (which is the top of the stack), we need to pop out the top element in the stack, so we get the number of elements larger than arr[1] continuously is (2 - 1 - 1) = 1. So res[1] = 0;

We will continue the comparison between the new top of the stack and arr[2]. Now the top is 0. and arr[0] == 6 > arr[2] == 3, so we need to pop it as well. So res[0] = 2 - 0  - 1= 1.

The stack becomes empty, so we just put 2 into it.

So far, we have obtained res[0] = 1 and res[1] = 0. Are they correct? 

It is straightforward that the answer is yes. For arr[0], there is one which is arr[1]; for arr[1], there is none.

Let continue the scan.

At step 4, index = 3, we have [2, 3];

             5,             4,                [2, 3, 4];

At step 6,              5, and we need to pop out elements again, since arr[5] < top of the stack

In this way, we can get all answers for every elements in a single scan!

The take-home message here is:

With a stack, we can get the number of the elements larger than every element on its right side continuously in one single scan!

Similarly, if we change the scanning direction, we can get the number of the elements larger than every element on its left side continuously in one scan as well.

After having these two values, we can calculate the number of sub-arrays with the current element as the minimum.

If the larger elements on the right side continuously is fr[i] and on the left side continuously is fl[i], then there are (fr[i] + 1) * (fl[i] + 1) sub-arrays with arr[i] as the minimum.

One corner case is when the array have elements with the same values. For example, the array is [5, 5, 5]. In this case, we can use a tiny trick: on the right side, we can calculate the number of elements no-smaller than the current element continuously; on the left side, we just calculate the number of elements strictly larger than the current element continuously.

For the [5, 5, 5] array, the fr array is [2, 1, 0], the fl array is [0, 0, 0].

So the number of the subarray with arr[0] as the minimum is: (2+1)*(0+1) = 3;

So the number of the subarray with arr[1] as the minimum is: (1+1)*(0+1) = 2;

So the number of the subarray with arr[2] as the minimum is: (0+1)*(0+1) = 1;

Similarly, we can count the number of the subarray with arr[i] as the maximum in O(N) as well (with a monotonically decreasing stack).

Once we figure out the frequency of the maximum elements and minimum elements, we can calculate the difference of all of them. (The order does not matter. Or we do not need to figure out the maximum and minimum of each subarray).

See the code below:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long res = 0;
        int n = nums.size();
        stack<int> sk1;
        vector<int> dp1(n, 0), dp2(n, 0), dp3(n, 0), dp4(n, 0);
        for(int i=0; i<n; ++i) {
            while(sk1.size() && nums[sk1.top()] > nums[i]) {
                int id = sk1.top();
                sk1.pop();
                dp1[id] = i - id;
            }
            sk1.push(i);
        }
        while(sk1.size()) {
            int id = sk1.top();
            sk1.pop();
            dp1[id] = n - id;
        }
        for(int i=n-1; i>=0; --i) {
            while(sk1.size() && nums[sk1.top()] >= nums[i]) {
                int id = sk1.top();
                sk1.pop();
                dp2[id] = id - i;
            }
            sk1.push(i);
        }
        while(sk1.size()) {
            int id = sk1.top();
            sk1.pop();
            dp2[id] = id + 1;
        }
        for(int i=0; i<n; ++i) {
            while(sk1.size() && nums[sk1.top()] < nums[i]) {
                int id = sk1.top();
                sk1.pop();
                dp3[id] = i - id;
            }
            sk1.push(i);
        }
        while(sk1.size()) {
            int id = sk1.top();
            sk1.pop();
            dp3[id] = n - id;
        }
        for(int i=n-1; i>=0; --i) {
            while(sk1.size() && nums[sk1.top()] <= nums[i]) {
                int id = sk1.top();
                sk1.pop();
                dp4[id] = id - i;
            }
            sk1.push(i);
        }
        while(sk1.size()) {
            int id = sk1.top();
            sk1.pop();
            dp4[id] = id + 1;
        }
        for(int i=0; i<n; ++i) {
            // cout<<dp1[i]<<" "<<dp2[i]<<" "<<dp3[i]<<" "<<dp4[i]<<endl;
            res += (long)nums[i] * ((dp3[i]) * (dp4[i]) - (dp1[i]) * (dp2[i]));
        }
        return res;
    }
};

We can make the code much more concise. 

With a monotonically non-decreasing stack, when we pop out one element, we can calculate the number of (strictly) larger elements on the left side continuously as well. To get this, we just need to compare the index popped out with the current top of the stack, or left boundary if stack if empty. (Why?)

See the code below:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long res = 0, n = nums.size();
        stack<int> sk;
        for(int i=0; i<=n; ++i) {
            while(sk.size() && (i==n || nums[sk.top()] > nums[i])) {
                int id = sk.top();
                sk.pop();
                int fr = i - id;
                int fl = sk.empty() ? id + 1 : id - sk.top();
                res -= (long long)nums[id]*fr*fl;
            }
            if(i<n) sk.push(i);
        }
        for(int i=0; i<=n; ++i) {
            while(sk.size() && (i==n || nums[sk.top()] < nums[i])) {
                int id = sk.top();
                sk.pop();
                int fr = i - id;
                int fl = sk.empty() ? id + 1 : id - sk.top();
                res += (long long)nums[id]*fr*fl;
            }
            if(i<n) sk.push(i);
        }
        return res;
    }
};

[Leetcode] 1980. Find Unique Binary String

1980. Find Unique Binary String

Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.

Constraints:

n == nums.length

1 <= n <= 16

nums[i].length == n

nums[i] is either '0' or '1'.

Analysis:

In order to reduce the time complexity, we need to,

1. store the existing strings in a unordered_set, which makes the checking in O(1);

2. save the visited string, to avoid infinite loop;

Then we can start with the first string, and try to flip each char, until we can find a brand new string.

See the code below:

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        unordered_set<string> st;
        for(auto &a : nums) st.insert(a);
        unordered_set<string> vis;
        string res = nums[0];
        while(st.count(res) > 0) {
            for(int i=0; i<n; ++i) {
                res[i] = res[i] ^ 1;
                if(vis.count(res)) continue;
                vis.insert(res);
                if(st.count(res)) break;
                return res;
            }
        }
        return res;
    }
};

[Leetcode] 1981. Minimize the Difference Between Target and Chosen Elements

 1981. Minimize the Difference Between Target and Chosen Elements

You are given an m x n integer matrix mat and an integer target.

Choose one integer from each row in the matrix such that the absolute difference between target and the sum of the chosen elements is minimized.

Return the minimum absolute difference.

The absolute difference between two numbers a and b is the absolute value of a - b.

Constraints:

m == mat.length

n == mat[i].length

1 <= m, n <= 70

1 <= mat[i][j] <= 70

1 <= target <= 800

Analysis:

Let look at the brute-force way: there are n^m combinations in total. If n == m == 70, this number could be as large as 70^70, which is too overwhelming...

We need to figure out some way with reduced complexity.

Bitset would be a good choice to this question. The key idea is to use the index of the bits representing the sums.

For example, if a bitset bt[80] = 1, meaning the bit at the index of 80 is 1, then there is a sum equal to 80.

Bitset has an important operation: bit shift.

When we need to add a number to many others sums, then bit shift would greatly reduce the time complexity: since one bit shift operation would shift all the bits in a bitset by only one operation! More details can be found here.

In this question, initially we can have a bitset to record all the elements in the first row: basically set the corresponding bits as 1.

Then move on to the next row. 

For each number in the second row, we need to add it to all the possible sums stored in the bitset from the previous row. Bit shift can perfectly handle this. After performing this bit shift operation to each number in the row, we need to store all the possible sums into a new bitset, which is needed for the next row. An or (|) operation is good enough for this.

We just repeat this step row by row, to the last row.

After finishing all of this, all the possible sums are stored in the last bitset. We just need to check all the possible sums, to see which one gives the minimum abs(sum - target).

See the code below:

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat.front().size(), cs = 40000, res = cs;
        bitset<40000> bt;
        for(int i=0; i<n; ++i) bt[mat[0][i]] = 1;
        for(int i=1; i<m; ++i) {
            bitset<40000> pre = bt, nxt;
            for(int j=0; j<n; ++j) {
                nxt |= pre << mat[i][j];
            }
            bt = nxt;
        }
        for(int i=0; i<cs; ++i) {
            if(bt[i]) res = min(res, abs(i-target));
        }
        return res;
    }
};

This question can also be solved by dfs + memo.  

memo[r][sum] means: the minimum abs(possible sums - target) starting with row number r and the starting sum value as sum.

The optimization lines and trim lines are needed, otherwise, it cannot pass the OJ.

See the code below:

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat.front().size();
        for(auto &a : mat) {
            sort(a.begin(), a.end());
        }
        sort(mat.begin(), mat.end(), greater());
        memset(memo, -1, sizeof(memo));
        return dfs(mat, 0, 0, target);
    }
private:
    int memo[71][4901];
    int dfs(vector<vector<int>>& ms, int r, int sum, int& target) {
        if(r == ms.size()) {
            return abs(sum - target);
        }
        if(memo[r][sum] != -1) return memo[r][sum];
        int res = INT_MAX;
        for(int i=0; i<ms[r].size(); ++i) {
            if(sum + ms[r][i] > target && abs(sum + ms[r][i] - target >= res)) break;
            res = min(res, dfs(ms, r+1, sum + ms[r][i], target));
        }
        return memo[r][sum] = res;
    }
};

Leetcode 312: Burst Balloons

 https://leetcode.com/problems/burst-balloons/description/

Notes:

This question is a very typical dp question. (in general, if a question can be down-size to a similar question, then it can be solved by dp)

One of the difficulties to this question is that the "boundary condition" is changing once we burst a balloon, since this balloon will disappear after the bursting.

One way to solve this is that: we can think about this question reversely. Instead of  starting from the first balloon to burst, we can start with the last balloon to burst.

The reason is that the last balloon will always has the fixed boundary condition. If we use dp[i][j] represents the maximum coins that we can obtained from [i, j] range, then

dp[i][j] = max(nums[i-1]*nums[k]*nums[j+1] + dp[i][k-1] + dp[k+1][j])

where k in the range of [i, j].

To simplify the coding,, we can insert 1 in the begin and end of the original array, respectively.

The time complexity is O(N^3), and the space complexity if O(N^2).

See the code below:

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        // insert 1 in the begin and end of nums
        // i, j in the range of [1, n]
        // dp[i][j] = max(nums[i-1]*nums[k]*nums[j+1] + dp[i][k-1] + dp[k+1][j])
        int n = nums.size();
        if(n==0) return 0;
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n+2, vector<int>(n+2, 0));
        for(int i=1; i<n+1; ++i) dp[i][i] = nums[i-1]*nums[i]*nums[i+1];
        for(int i=n; i>0; --i) {
            for(int j=i+1; j<n+1; ++j) {
                for(int k=i; k<=j; ++k) {
                    dp[i][j] = max(dp[i][j], nums[i-1]*nums[k]*nums[j+1] + dp[i][k-1] + dp[k+1][j]);
                }
            }
        }
        return dp[1][n];
    }
};

Leetcode 1584: Min Cost to Connect All Points

 https://leetcode.com/problems/min-cost-to-connect-all-points/description/

Notes:

[udpate 2020-09-13]

In the first method (see below), we keep a very large priority queue, which actually is not necessary. 

Here is a better way to maintain the information in the spanning process. 

1): will use a vector to label whether a node is connected or not. (index for node, value for connected condition: 1 for connected, 0 for dis-connected);

2): will use a second vector to label the shortest distance for a dis-connected node to all the connected nodes. This needs to be updated when a new node becomes connected.

But the basic idea is the same: find the node (or point) having the shortest distance to the nodes already connected.

See the code below:

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), res = 0;
        vector<int> used(n, 0), mxs(n, INT_MAX);
        mxs[0] = 0;
        for(int i=0; i<n; ++i) {
            // find the next node with the shortest distance
            int id = 0, mm = INT_MAX;
            for(int j=0; j<n; ++j) {
                if(!used[j] && mxs[j] < mm) {
                    id = j;
                    mm = mxs[j];
                }
            }
            used[id] = 1;
            res += mm;
            // update mxs (since a new element at id is added in, so just need to update the shortest dis to it)
            for(int j=0; j<n; ++j) {
                if(used[j]) continue;// if connected already, continue
                int dis = abs(points[id][0] - points[j][0]) + abs(points[id][1] - points[j][1]);
                if(dis < mxs[j]) mxs[j] = dis;
            }
        }
        return res;
    }
};

This is question can be viewed as a variation of minimum spanning tree. In some sense, it is also similar to Dijkstra algorithm.

Since eventually we need to connect all the nodes, so it does not matter starting with which one.

Similar to Dijkstra, we will have a connected pool: set, and the distance rank: a reversed priority queue.

Let start with points[0], 

1): then we will choose the point with the shortest distance with points[0] as the next one;

so a reversed priority_queue can be used;

2): after having the second points, we need to put all the distance from the second points to the rest points into the priority_queue;

3): the top of the priority_queue should always be the next points to be connected (this is exactly the same as Dijkstra)

4): after having the next points, we should update all the available distances into the priority_queue...

until all the nodes are connected.

Since we have a set to record the connected nodes, so we just can use this to avoid duplicated visiting.

See the code below:

class Solution {
public:
    typedef pair<int, int> pi;
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), res = 0;
        priority_queue<pi, vector<pi>, greater<pi>> pq;
        set<int> st;
        st.insert(0);
        for(int i=1; i<n; ++i) {
            int dis = abs(points[0][0] - points[i][0]) + abs(points[0][1] - points[i][1]);
            pq.push({dis, i});
        }
        while(st.size() < n) {
            while(st.count(pq.top().second)) pq.pop();
            if(pq.empty()) break;
            auto t = pq.top();
            int d = t.first, id = t.second;
            res += d;
            // cout<<res<<" "<<d<<endl;
            st.insert(id);
            for(int i=0; i<n; ++i) {
                if(st.count(i)) continue;
                int dis = abs(points[id][0] - points[i][0]) + abs(points[id][1] - points[i][1]);
                pq.push({dis, i});
            }
        }
        return res;
    }
};

Leetcode 1448: Count Good Nodes in Binary Tree

 https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/

Notes:

This question is quick straightforward: top-down recursion.

And we need to pass down the maximum value so far during recursion.

Please see the code below:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int goodNodes(TreeNode* root) {
        return !root ? 0 : dfs(root, root->val);
    }
private:
    int dfs(TreeNode* r, int val) {
        return !r ? 0 : (r->val >= val ? 1 : 0) + dfs(r->left, max(r->val, val)) + dfs(r->right, max(r->val,val));
    }
};

Leetcode 1559: Detect Cycles in 2D Grid

 https://leetcode.com/problems/detect-cycles-in-2d-grid/description/

Notes:

This question belongs to find the connected groups. One way is that we can use union-find, (or bfs, or dfs).

One of the features about the circle is that: each element on the circle has at least 2 neighbors with the same letter. So the in-degree is 2 or larger.

This can give us a way to solve this problem: 

1): we can label all the elements with in-degree less than 2 to be invalid. 

2): then we can just perform "find island" with the elements with in-degree >= 2 only;

3): if there is any "island" or connected group having a size larger > 3, return true;

4): o/w, return false; 

So step 1) is the key. One difficulty is that: say there is one element has an in-degree larger than 1, but if one or more of its neighbors (with the same letter) only has an in-degree of 1, then the in-degree of the element will be decreased by removing the invalid neighbors.

We can apply bfs to gradually label all the elements as invalid. The logic here is similar to topology sort: we will start with elements with in-degree of 1. Then gradually search its four neighbors:

1): if the neighbor is not the same letter, continue;

2): else if the neighbor has a positive in-degree, then update it by minus 1;

After handling all the four neighbors, we need to scan the four neighbor again to see the final in-degrees. If the in-degree is 1, we will push it to the bfs queue; o/w, continue (if < 1, this element has no effect on others; if >1, still belongs to valid group).

After finishing this step, all the remaining elements with in-degree > 2 will be the pool to forme "islands" or connected groups. If any of the island has a size larger than 3, return true; o/w, return false.

Here use the union-find algorithm for finding circles.  

See the code below:

class Solution {
struct UF {
    vector<int> ps, cts;
    int num, mx;
    UF(int n): ps(n, 0), cts(n, 1), num(n), mx(0) {
        iota(ps.begin(), ps.end(), 0);
        if(n>0) mx = 1;
    }
    int find(int x) {
        if(ps[x] == x) return x;
        return ps[x] = find(ps[x]);
    }
    void unite (int x, int y) {
        int a = find(x), b = find(y);
        if(a != b) {
            ps[b] = a;
            cts[a] += cts[b];
            mx = max(mx, cts[a]);
            --num;
        }
    }
};
public:
    bool containsCycle(vector<vector<char>>& grid) {
        if(!grid.size() || !grid.front().size()) return false;
        int m = grid.size(), n = grid.front().size();
        vector<int> dirs = {-1, 0, 1, 0, -1};
        vector<vector<int>> ids(m, vector<int>(n, 0));
        queue<pair<int, int>> q;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                for(int k=0; k+1<dirs.size(); ++k) {
                    int a = i + dirs[k], b = j + dirs[k+1];
                    if(a<0 || a>=m || b<0 || b>=n || grid[a][b] != grid[i][j]) continue;
                    ++ids[i][j];
                }
                if(ids[i][j] == 1) q.push({i, j});
            }
        }
        while(q.size()) {
            auto t = q.front();
            q.pop();
            int x = t.first, y = t.second;
            --ids[x][y];
            for(int k=0; k+1<dirs.size(); ++k) {
                int a = x + dirs[k], b = y + dirs[k+1];
                if(a<0 || a>=m || b<0 || b>=n) continue;
                if(grid[a][b] == grid[x][y] && ids[a][b] > 0) --ids[a][b];
            }
            for(int k=0; k+1<dirs.size(); ++k) {
                int a = x + dirs[k], b = y + dirs[k+1];
                if(a<0 || a>=m || b<0 || b>=n || grid[a][b] != grid[x][y] || ids[a][b] != 1) continue;
                q.push({a, b});
            }
        }
        UF uf(m*n);
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(ids[i][j] < 2) continue; 
                int a = i-1, b = j-1;
                // upper 
                if(a>=0 && grid[a][j] == grid[i][j] && ids[a][j] > 1) uf.unite(a*n+j, i*n+j);
                // left
                if(b>=0 && grid[i][b] == grid[i][j] && ids[i][b] > 1) uf.unite(i*n+b, i*n+j);
            }
        }
        return uf.mx > 3;
    }
};

Leetcode 1585: Check If String Is Transformable With Substring Sort Operations

 https://leetcode.com/problems/check-if-string-is-transformable-with-substring-sort-operations/description/

Notes:

There are only 10 types of letters, so one way is that we can handle them one by one.

One of the key observations for sorting sub-string (or any type of ascending sorting): the id of the largest element will no way get smaller (or the position cannot be moved forward in an ascending sort).

Based on this, we can just start with the largest letter, then the second largest one, ... until all done.

Let take '9' as an example, 

1): say there are 3 '9's in s and also 3 in t (if not, return false directly);

2): then the id of the 1st '9' in s should be <= the id of the 1st '9' in t (if not, return false. Why? since there is no way the id of the 1st '9' in s becomes smaller due to sorting (or there is no bigger letter than '9'));

3): then the id of the 2nd '9' in s should be <= the id of the 2nd '9' in t (if not, return false);

...

If all satisfy, then we can remove all '9' from s and t, then recursively run the same procedure but with a smaller size.

After removing all '9's, the next one is '8', ...

If all can be removed, return true.

[update: 2024/11/27] 

As commented @Kaisar below, there is a case ("891", "198") cannot pass.

We can just apply the same logic but with the reversed order: starting from '0', then the id of the smallest element will no way get larger.

When the results from both directions are true, return true. 

See the code below:

class Solution {
public:
    bool isTransformable(string s, string t) {
        string s1 = s, t1 = t;
        // check ids of elements from largest to smallest;
        for(char c='9'; c>='0'; --c) {
            vector<int> ids1, ids2;
            for(int i=0; i<s1.size(); ++i) {
                if(s1[i] == c) ids1.push_back(i);
                if(t1[i] == c) ids2.push_back(i);
            }
            if((int)ids1.size() != (int)ids2.size()) return false;
            for(int i=0; i<ids1.size(); ++i) {
                if(ids1[i] > ids2[i]) return false;
            }
            string s2 = "", t2 = "";
            for(auto &a : s1) {
                if(a < c) s2.push_back(a);
            }
            for(auto &a : t1) {
                if(a < c) t2.push_back(a);
            }
            s1 = s2;
            t1 = t2;
        }
        // check ids of elements from smallest to the largest;
        s1 = s, t1 = t;
        for(char c='0'; c<='9'; ++c) {
            vector<int> ids1, ids2;
            for(int i=0; i<s1.size(); ++i) {
                if(s1[i] == c) ids1.push_back(i);
                if(t1[i] == c) ids2.push_back(i);
            }
            if((int)ids1.size() != (int)ids2.size()) return false;
            for(int i=0; i<ids1.size(); ++i) {
                if(ids1[i] < ids2[i]) return false;
            }
            string s2 = "", t2 = "";
            for(auto &a : s1) {
                if(a > c) s2.push_back(a);
            }
            for(auto &a : t1) {
                if(a > c) t2.push_back(a);
            }
            s1 = s2;
            t1 = t2;
        }
        return true;
    }
};

Leetcode 650: 2 Keys Keyboard

 https://leetcode.com/problems/2-keys-keyboard/description/

Notes:

This question is a weaker version of Leetcode 651 (4 Keys Keyboard), but the idea is similar: 

      if we have solved the same question with a smaller n, then we should think about how to use the calculated results directly.

Let say we have solved all the smaller dp's with a smaller indexes than i, now we want to calculate dp[i].

Here dp[i] means the minimum number of steps to get n 'A's.

If we have dp[j], and i%j == 0, then one way to get dp[i] is: dp[j] + i/j. Why?

We just simply Ctr-C once on j 'A's, then (Ctr-V i/j  - 1) times. So the overall is dp[j] + i/j.

if(i%j != 0) then we cannot get i 'A's from j 'A'  (I will leave this to you to prove...)

Now the question becomes clear: we just need to go though all the smaller ones (which has been calculated at this moment), then find the smallest value.

There is maybe a even faster way to do this, keep tuned.

See the code below:

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n+1, 0);
        for(int i=2; i<=n; ++i) {
            dp[i] = n;
            for(int j=1; j*2<=i; ++j) {
                if(i%j==0) dp[i] = min(dp[i], dp[j] + i/j); 
            }
        }
        return dp[n];
    }
};

Leetcode 651: 4 Keys Keyboard

 Imagine you have a special keyboard with the following keys:

Key 1: (A): Print one 'A' on screen.

Key 2: (Ctrl-A): Select the whole screen.

Key 3: (Ctrl-C): Copy selection to buffer.

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.

Example 1:

Input: N = 3
Output: 3
Explanation: 
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

 

Example 2:

Input: N = 7
Output: 9
Explanation: 
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

 

Note:

1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

Notes:

This question can be solved by dp.

Imagine that we have solved all the smaller one than i, now we need to solve dp[i].

dp[i] means the maximum number of A that can be printed.

then dp[i] can be derived from the solved dp's but with a smaller index.

If j is one of them, and dp[j] is solved, and j < i

Then dp[i] could be dp[j] * (i - j -1). Why?

Because we need to Ctr-A and Ctr-C before we can Ctr-V. For example, we have dp[3], then dp[5] could be dp[3]*(5 - 3 -1) = dp[3] (which obviously is not the optimal choice. A different way is that we can simply add two As directly (using key 1) after dp[3] which can give dp[3] + 2 for dp[5].)

Thus, in order to find the optimal choice, one way is that we can go through all the smaller ones by the above two ways:

1): use key2 + key3 + kye4s,  (this could be true for larger i), the formula for this is:

      dp[j] * (i - j -1)

2): use key1 directly, (this could be true for smaller i)

       dp[j] + (i - j)

If we decide to go through all the dp's with indexes smaller than i, then it meas the time complexity is O(N^2). In this question, N <= 50, so it should be Okay.

See the code below:

class Solution {
public:
    /**
     * @param N: an integer
     * @return: return an integer
     */
    int maxA(int N) {
        // write your code here
        vector<int> dp(N+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=N; ++i) {
            for(int j=0; j<i; ++j) {
                dp[i] = max(dp[i], dp[j] + i - j);
                if(j+3<i) dp[i] = max(dp[i], dp[j]*(i-j-1));
            }
        }
        return dp[N];
    }
};

 

Leetcode 1400: Construct K Palindrome Strings

 https://leetcode.com/problems/construct-k-palindrome-strings/description/

Notes:

This question seems not easy, but actually is not.

We just need to use one property of palindrome: at most there is one letter with odd count.

Thus, in order to form k palindromes, at most we have k letters with odd count.

If the size of string is smaller than k, there is no way to form k palindrome.

See the code below:

class Solution {
public:
    bool canConstruct(string s, int k) {
        int n = s.size(), res = 0;
        if(n<k) return false;
        if(n==k) return true;
        vector<int> ct(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        for(auto &a : ct) {
            if(a & 1) ++res;
        }
        return res <= k;
    }
};

Leetcode 1558: Minimum Numbers of Function Calls to Make Target Array

 https://leetcode.com/problems/minimum-numbers-of-function-calls-to-make-target-array/description/

Notes:

This question can be solved greedily: 

1): if there is one element is odd, we need to reduce 1 to make it even; 

2): when all even, we can divide it by 2 

Since 2) is always faster than 1, so we need to do operation 2) whenever it is possible.

See the code below:

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int res = 0;
        bool largerThan0 = true, allEven = true;
        while(largerThan0) {
            largerThan0 = false;
            allEven = true;
            for(auto &a : nums) {
                if(a>0) largerThan0 = true;
                if(a&1) {
                    --a;
                    ++res;
                    allEven = false;
                }
            }
            if(largerThan0 && allEven) {
                for(auto &a : nums) a /= 2;
                ++res;
                largerThan0 = true;
            }
        }
        return res;
    }
};

Leetcode 358: Rearrange String K Distance Apart

 https://leetcode.com/problems/find-latest-group-of-size-m/description/

Notes:

This question is very similar as another question Leetcode 621 (since I solved that question first...)

The basic idea is the same: we need to find the letter with the largest count (m), then for the first (m-1) we have to place (m-1)*k letters (including the letter with the maximum count). 

Then for the last one letter, we do not need to keep it k distance apart from the next one (since there is no next one...). If there is no letter with the tied maximum counting, we just need to add 1 (the letter itself), but if there are n letters with the maximum counting, then the need to add n more letters, to list all the letter with k distance apart.

The overall letters need are (m-1)*k + n. If this value is larger than the size of the string, then there is not enough letters to maintain k distance apart: means that this is impossible. Otherwise, it is okay to form an valid one.

Since this question requests to return one final string, so we can consider to use a priority queue for valid ones: 

1): every time, we pick up one with the largest counting; 

2): and we keep this until we have pop out k different letters. This will form one valid "k-distance" apart substring; 

3): then we need to put the previous pop-out elements back to the priority queue, if their size still larger than 1 after removing 1.

4): repeat this process until there is no element remaining in the queue.

See the code below:

class Solution {
public:
    string rearrangeString(string str, int k) {
        if (k == 0) return str;
        string res;
        int len = (int)str.size(), mx = 0, rep = 0;
        unordered_map<char, int> m;
        priority_queue<pair<int, char>> q;
        for (auto a : str) ++m[a];
        for (auto it = m.begin(); it != m.end(); ++it) {
            q.push({it->second, it->first});
            // find the maximum counting, and the numer of letters having this 
	    if (it->first > mx) {
                mx = it->first;
                rep = 1;
	    } else if (it->first == mx) {
                ++rep;   
            }
        }
        // if need more letters than itself, then cannot construct an valid one
        if((m-1)*k + rep > len) return "";
        while (!q.empty()) {
            vector<pair<int, int>> v;
            int cnt = min(k, len);
            for (int i = 0; i < cnt; ++i) {
                if (q.empty()) return "";
                auto t = q.top(); q.pop();
                res.push_back(t.second);
                if (--t.first > 0) v.push_back(t);
                --len;
            }
            for (auto a : v) q.push(a);
        }
        return res;
    }
};

 

Leetcode 1542: Find Longest Awesome Substring

 https://leetcode.com/problems/find-longest-awesome-substring/description/

Notes:

This question is similar to another question, Leetcode 1371

The basic idea is the same: use a mask to memorize the counting of each letters. In this question, the letters are numbers from 0 to 9. 

Then we need to know whether the counting of each letter is even or odd. So we can use a bit to indicate this. For each bit, 0 means even count; 1 means odd.

If the same mask shows up again, then the substring between these two masks should have even numbers of every letter; and this is what we need to construct a palindrome.

Another possible situation for a palindrome is to have one letter with odd counting. This can also be checked by add one more letter (for each kind) to the mask.

See the code below:

class Solution {
public:
    int longestAwesome(string s) {
        int n = s.size(), res = 0, mask = 0;
        vector<int> dp(1<<10, -2);
        dp[0] = -1;
        for(int i=0; i<n; ++i) {
            mask ^= 1<<(s[i] - '0');
            if(dp[mask] != -2) res = max(res, i - dp[mask]);
            else dp[mask] = i;// memorize the first position
            for(int j=0; j<10; ++j) {// check one letter with odd count
                int t = mask ^ (1<<j);
                if(dp[t] != -2) res = max(res, i - dp[t]);
            }
        }
        return res;
    }
};

Leetcode 730: Count Different Palindromic Subsequences

 https://leetcode.com/problems/count-different-palindromic-subsequences/description/

Notes:

[update]:    3-dimensional dp

The two dimensional dp  (see the second method) is not easy to understand, a better way (in rationalization) is to use a three dimensional dp.

There is one condition that has not been used: there are only 4 types of letter.

So we can define a dp[i][j][k], meaning the unique number of palindrome ending with letter (k + 'a') in the range of [i, j].  Since it is palindrome, so it should start with (k+'a') as well.

Then the total number of unique palindromes in the range of [i, j] should be the Sum (dp[i][j][k]) over all k values.

Now let us look at the transition formula:

1): if(i>j) dp[i][j][k] = 0;

2): if(i==j && s[i] == k + 'a')  dp[i][j][k] = 1;

3): if (s[i] != s[j])  dp[i][j][k] = dp[i+1][j][k] + dp[i][j-1][k] - dp[i+1][j-1][k];

4): if (s[i] == s[j])  dp[i][j][k] = 2 + Sum (dp[i+1][j-1][a]), where a can be all letters. 

     (note: 2 for single "s[i]" and double "s[i]s[j]")

See the code below:

class Solution {
public:
    int countPalindromicSubsequences(string S) {
        int n = S.size(), mod = 1e9+7;
       // vector<vector<vector<long>>> dp(n, vector<vector<long>>(n, vector<long>(4, 0)));
        for(int i=0; i<n; ++i) dp[i][i][S[i]-'a'] = 1;
        
        for(int i=n-2; i>=0; --i) {
            for(int j=i+1; j<n; ++j) {
                for(int k=0; k<4; ++k) {
                    if(S[i] != S[j] || S[i] != (k + 'a')) {
                        dp[i][j][k] = (dp[i][j][k] + dp[i+1][j][k] + dp[i][j-1][k] - dp[i+1][j-1][k] + mod)%mod;
                    }
                    else {
                        dp[i][j][k] = (dp[i][j][k] + 2)%mod;
                        for(int t=0; t<4; ++t) {
                            dp[i][j][k] = (dp[i][j][k] + dp[i+1][j-1][t])%mod;
                        }
                    }
                }
            }
        }
        long res = 0;
        for(int i=0; i<4; ++i) {
            res = (res + dp[0][n-1][i])%mod;
        }
        return res;
    }
private:
    int dp[1000][1000][4];
};

 2-dimensional dp

This question is not easy to solve. Even though it may indicate using dp, but it is not easy to derive the correct state transition formula. 

One of the difficulties is how to avoid duplicated counting. If we distinguish the palindromes by their indexes in the string rather than themselves, then this question becomes relative easier. So let start with this first.

number of palindromes distinguished by their indexes in the string

Let use dp[i][j] to represent the number of palindromes in the range [i, j] with i <= j. Then,

1): if s[i] != s[j], dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];

2): if s[i]== s[j], we have to choices: a): using s[i] and s[j]; b): not using s[i] and s[j]

Apparently, b) is the same as the case in 1). And in a), all the palindrome have to start with s[i] and end with s[j]. Thus, there are dp[i+1][j-1] + 1 in total. The 1 means "s[i]s[j]".

So the total palindromes in case 2) is:  number in a) + number in b)

       dp[i+1][j-1] + 1 + dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] = dp[i+1][j] + dp[i][j-1] +1.

But this is not what this question asks about! In this question, distinguished palindromes are defined by their letters not by their indexes in the string. So we need to remove the duplicates.

number of palindromes distinguished by their letters

To start, let us define two kinds of dps: one is dp[i][j], another one is bp[i][j].

dp[i][j]: means the number of unique palindromes in the range [i, j] not necessary starting with the ith letter and ending with the jth letter;

bp[i][j]: means the number of unique palindromes in the range [i, j] starting with the ith letter and ending with the jth letter;

Then let re-look at the two situations we had analyzed above:

1): when s[i] != s[j], then dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

2): when s[i] == s[j], we still have two cases: a): using s[i] and s[j]; b) not using s[i] and s[j]

Based on our destinations above, a) is bp[i][j] = dp[i+1][j-1] + 1, and b) is dp[i+1][j] + dp[i][j-1] - (duplicated part). If there are still duplicates between a) and b), we still need to remove them.

There are another three different situations for 2). 

(i) when there is no more s[i] letter in the range of [i+1, j-1]

     in this case, the count in b) is:

         dp[i+1][j] = dp[i+1][j-1] + 1   (1 for s[i])

         dp[i][j-1] = dp[i+1][j-1] + 1    (1 for s[j]) 

     Thus, the duplicated part is  dp[i+1][j-1] + 1   (since s[i] and s[j] are the same).

     So the total count for b) is  dp[i+1][j-1] + 1.

    

      Now let check the overlap between a) and b). In a), palindrome has to start with s[i] and end with s[i] as well, so there is no overlap between them. 

      Thus, the overall count is:  union( a + b)

      union(bq[i][j]   +  dp[i+1][j-1] + 1)  = dp[i+1][j-1] + 1 + dp[i+1][j-1] + 1 

       = 2*dp[i+1][j-1] + 2

(ii) there is only one more s[i] letter in the range [i+1, j-1], let say it is s[k], where i<k<j.

      then the count for b) is:

       dp[i+1][j] = dp[i+1][j-1] + bp[k][j],   the single "s[i]" has been included in dp[i+1][j-1], s[i] == s[k]

       dp[i][j-1] = dp[i+1][j-1] + bp[i][k],    the single "s[i]" has been included in dp[i+1][j-1], s[i] == s[k]

      Apparently, one overlap part between dp[i+1][j] and dp[i][j-1] is dp[i+1][j-1], so we just take one of them in the final counting. 

      But how to deal with bp[k][j] and bp[i][k]? They may have overlap as well!

      It seems very complicated, but actually is not. Since we have to remove the duplicates between 1) and 2) as well, so we just look at 1) first. In 1): the total counting (before removing duplicates with 2))  is bp[i][j]. It is easy to tell that both bp[k][j] and bp[i][k] are subsets of bp[i][j]. Thus, both of them can be removed directly!

      Then, the overall count becomes:  union( a + b)

      

       union(bq[i][j]   +  dp[i+1][j-1] + bp[k][j] + bp[i][k]) = dp[i+1][j-1] + 1 + dp[i+1][j-1] 

       = 2 * dp[i+1][j-1] + 1

(iii) where there are more than 1 s[i] letter in the range of [i+1, j-1]. 

        Let say, s[l] and s[r], i<l<r<j, and

        s[l] is the first letter equals to s[i] from the left in the range of [i+1, j-1];

        s[r] is the first letter equals to s[i] from the right in the range of [i+1, j-1];

       then the count for b) is:

       dp[i+1][j] = dp[i+1][j-1] + bp[l][j],   both single "s[i]" and "s[i]s[j]" have been included in dp[i+1][j-1],  due to that s[l] == s[r] == s[i];

       dp[i][j-1] = dp[i+1][j-1] + bp[i][r],   both single "s[i]" and "s[i]s[j]" have been included in dp[i+1][j-1],  due to that s[l] == s[r] == s[i].

        Similar to (ii), both bp[l][j] and bp[i][r] can be removed directly, since both of them are the subsets to bp[i][j]. For b) only one dp[i+1][j-1] remaining. Is there more overlap between a) and b)?

         The answer is yes. 

         dp[i][j-1] should include bp[l][r], and bp[i][j] should also include bp[l][r].

         Thus, we need to remove one bp[l][r] by - bp[l][r] = -(dp[l+1][r-1] + 1);

         Then the overall union is:  union( a + b)

        union(bq[i][j]   +  dp[i+1][j-1] + bp[l][j] + bp[i][r]) = union(bq[i][j] +  dp[i+1][j-1])

        = union (dp[i+1][j-1] + 1 + dp[i+1][j-1] - bq[l][j] - 1) =

        = 2 * dp[i+1][j-1]  - dp[l+1][r-1]

In summary, the station transition formula are:

1): if s[i] != s[j], dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];

2): if s[i] == s[j],

      a): if there is no more letter s[i] in [i+1, j-1]

            dp[i][j] = 2 * dp[i+1][j-1] + 2;

      b): if these is only one letter s[i] in [i+1, j-1]

            dp[i][j] = 2 * dp[i+1][j-1] + 1;

      c): if there are 2 or more letter s[i] in [i+1, j-1]

           dp[i][j] = 2 * dp[i+1][j-1]  - dp[l+1][r-1]. (for the meaning of l and r, see the above analysis)

See the code below:

class Solution {
public:
    int countPalindromicSubsequences(string S) {
        int n = S.size(), mod = 1e9+7;
        vector<vector<long>> dp(n+1, vector<long>(n, 0));
        for(int i=0; i<n; ++i) dp[i][i] = 1;
        for(int i=n-2; i>=0; --i) {
            for(int j=i+1; j<n; ++j) {
                if(S[i] != S[j]) dp[i][j] = (dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + mod)%mod;
                else {
                    int left = i + 1, right = j-1;
                    while(left<n && S[left] != S[i]) ++left;
                    while(right>=0 && S[right] != S[i]) --right;
                    if(left>right) dp[i][j] = (dp[i+1][j-1]*2 + 2)%mod;
                    else if(left == right) dp[i][j] = (dp[i+1][j-1]*2 + 1)%mod;
                    else dp[i][j] = (dp[i+1][j-1]*2 - dp[left+1][right-1] + mod)%mod;
                }
            }
        }
        return dp[0][n-1];
    }
};

Leetcode 1419: Minimum Number of Frogs Croaking

 https://leetcode.com/problems/minimum-number-of-frogs-croaking/description/

Notes:

This question can be solved in a greedy way.

We need to record some key information during scanning. 

For example, 

1): once we meet with a 'c', we should see whether there are available frog or not. If yes, no new frog is needed; otherwise, need a new frog;

2): once we meet with a 'r', we need to make sure there is at least one frog is yelling 'c'. If no, return -1;

if yes, need to update the counting on 'r' and 'c', respectively;

3): if 'o' or 'a', then it is similar to 2);

4): if 'k', similar to 2). but once difference is that: we only need to update the counting on 'a'. Then one more frog becomes available for the next round of yelling;

5): after scanning the string, we need to make sure all the frogs finish their yelling. This is can be done by scanning the counting of each letter. If all zero, it means all done; o/w, return -1.

6): return number of frog needed.

See the code below:

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int n = croakOfFrogs.size(), res = 0, rm = 0;
        unordered_map<char, int> mp;
        for(auto &c : croakOfFrogs) {
            if(c=='c') {
                if(rm>0) --rm;
                else ++res;
                ++mp['c'];
            } else if(c == 'r') {
                if(!check(mp, 'c', 'r')) return -1;
            } else if(c == 'o') {
                if(!check(mp, 'r', 'o')) return -1;
            } else if(c == 'a') {
                if(!check(mp, 'o', 'a')) return -1;
            } else if(c == 'k') {
                if(!mp.count('a') || mp['a'] == 0) return -1;
                --mp['a'];
                ++rm;
            } else {
                return -1;
            }
        }
        for(auto &a : mp) {
            if(a.second > 0) return -1;
        }
        return res;
    }
private:
    bool check(unordered_map<char, int>& mp, char a, char b) {
        if(!mp.count(a) || mp[a] == 0) return false;
        --mp[a];
        ++mp[b];
        return true;
    }
};

Leetcode 1371: Find the Longest Substring Containing Vowels in Even Counts

 https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/description/

Notes:

This question can be solved by a method similar to "how many sub-array sum equals to a target value". If you have question about this, we can go step by step.

The naive method is to scan all the sub-strings, and then check the counts in each sub-string, and find the longest one. This needs O(n^2) time, so this is the upper-bound for this question.

Actually the largest case is n = 5 x 10^5, so we need a better method.

Let think about one letter only: what is the longest sub-string containing even count of one specific letter?

There are many ways to do this, but in order to achieve O(n) time complexity, we can use a bit to represents the count of the letter: 0 for even, 1 for odd. Then as we scan through the string, at each position, we know the count is even or odd. 

If even: the current longest sub-string is from the first even to the current position;

if odd:  the current longest sub-string is from the first odd to the current position.

Now, we need to monitor five letters, but the idea is the same. We just use a bit mask to replace one bit.

If we use a bit mask to record the counts of each letter; 0 for even, 1 for odd, then when the mask appear again, the sub-string between these two mask should contain even number of each letter.

One hash-map can be used to record the position (or index) of each mask when it appears for the first time, since we need this information to calculate the length of the current longest valid sub-string.

See the code below:

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int res = 0, n = s.size(), mask = 0;
        vector<int> dp(1<<5, s.size());// only 5 letters, so 5 bits
        dp[0] = -1;// special case for boundary condition
        for(int i=0; i<n; ++i) {
            char a = s[i];
            if(a=='a') mask ^= 1<<0;
            else if(a=='e') mask ^= 1<<1;
            else if(a=='i') mask ^= 1<<2;
            else if(a=='o') mask ^= 1<<3;
            else if(a=='u') mask ^= 1<<4;
            res = max(res, i - dp[mask]);
            dp[mask] = min(i, dp[mask]);// record the first position
        }
        return res;
    }
};