Huahua’s Tech Road

花花酱 LeetCode 1773. Count Items Matching a Rule

By zxi on February 27, 2021

You are given an array items, where each items[i] = [type_i, color_i, name_i] describes the type, color, and name of the i^th item. You are also given a rule represented by two strings, ruleKey and ruleValue.

The i^th item is said to match the rule if one of the following is true:

ruleKey == "type" and ruleValue == type_i.
ruleKey == "color" and ruleValue == color_i.
ruleKey == "name" and ruleValue == name_i.

Return the number of items that match the given rule.

Example 1:

Input: items = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]], ruleKey = "color", ruleValue = "silver"
Output: 1
Explanation: There is only one item matching the given rule, which is ["computer","silver","lenovo"].

Example 2:

Input: items = [["phone","blue","pixel"],["computer","silver","phone"],["phone","gold","iphone"]], ruleKey = "type", ruleValue = "phone"
Output: 2
Explanation: There are only two items matching the given rule, which are ["phone","blue","pixel"] and ["phone","gold","iphone"]. Note that the item ["computer","silver","phone"] does not match.

Constraints:

1 <= items.length <= 10⁴
1 <= type_i.length, color_i.length, name_i.length, ruleValue.length <= 10
ruleKey is equal to either "type", "color", or "name".
All strings consist only of lowercase letters.

Solution: Brute Force

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {

return count_if(begin(items), end(items), [&](const auto& item) {

return (ruleKey == "type" && item[0] == ruleValue

|| ruleKey == "color" && item[1] == ruleValue

|| ruleKey == "name" && item[2] == ruleValue);

});

}

};

花花酱 LeetCode 1771. Maximize Palindrome Length From Subsequences

By zxi on February 21, 2021

You are given two strings, word1 and word2. You want to construct a string in the following manner:

Choose some non-empty subsequence subsequence1 from word1.
Choose some non-empty subsequence subsequence2 from word2.
Concatenate the subsequences: subsequence1 + subsequence2, to make the string.

Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.

A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.

A palindrome is a string that reads the same forward as well as backward.

Example 1:

Input: word1 = "cacb", word2 = "cbba"
Output: 5
Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.

Example 2:

Input: word1 = "ab", word2 = "ab"
Output: 3
Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.

Example 3:

Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: You cannot construct a palindrome from the described method, so return 0.

Constraints:

1 <= word1.length, word2.length <= 1000
word1 and word2 consist of lowercase English letters.

Solution: DP

Let s = word1 + word2, build dp table on s. We just need to make sure there’s at least one char from each string.

Time complexity: O((m+n)^2)
Space complexity: O((m+n)^2)

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

string s = word1 + word2;

const int n = l1 + l2;

vector<vector<int>> dp(n, vector<int>(n));

for (int i = 0; i < n; ++i) dp[i][i] = 1;

for (int l = 2; l <= n; ++l)

for (int i = 0, j = i + l - 1; j < n; ++i, ++j) {

if (s[i] == s[j])

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

else

dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

}

int ans = 0;

for (int i = 0; i < l1; ++i)

for (int j = 0; j < l2; ++j)

if (word1[i] == word2[j])

ans = max(ans, dp[i][l1 + j]);

return ans;

}

};

O(m+n) Space complexity

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

string s = word1 + word2;

const int n = l1 + l2;

vector<int> dp1(n, 1), dp2(n);

int ans = 0;

for (int l = 2; l <= n; ++l) {

vector<int> dp(n);

for (int i = 0, j = i + l - 1; j < n; ++i, ++j) {

if (s[i] == s[j]) {

dp[i] = dp2[i + 1] + 2;

if (i < l1 && j >= l1)

ans = max(ans, dp[i]);

} else {

dp[i] = max(dp1[i + 1], dp1[i]);

}

// dp2, dp1 = dp1, dp

dp1.swap(dp);

dp2.swap(dp);

}

return ans;

}

};

花花酱 LeetCode 1770. Maximum Score from Performing Multiplication Operations

By zxi on February 21, 2021

You are given two integer arrays nums and multipliersof size n and m respectively, where n >= m. The arrays are 1-indexed.

You begin with a score of 0. You want to perform exactly m operations. On the i^th operation (1-indexed), you will:

Choose one integer x from either the start or the end of the array nums.
Add multipliers[i] * x to your score.
Remove x from the array nums.

Return the maximum score after performing m operations.

Example 1:

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
- Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

Example 2:

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:
- Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.

Constraints:

n == nums.length
m == multipliers.length
1 <= m <= 10³
m <= n <= 10⁵
-1000 <= nums[i], multipliers[i] <= 1000

Solution: DP

dp(i, j) := max score we can get with nums[i~j] left.

k = n – (j – i + 1)
dp(i, j) = max(dp(i + 1, j) + nums[i] * multipliers[k], dp(i, j-1) + nums[j] * multipliers[k])

Time complexity: O(m*m)
Space complexity: O(m*m)

C++/Top-Down

// Author: Huahua

class Solution {

public:

int maximumScore(vector<int>& nums, vector<int>& multipliers) {

const int m = multipliers.size();

const int n = nums.size();

vector<vector<int>> cache(m, vector<int>(m, INT_MIN));

function<int(int, int)> dp = [&](int i, int j) {

const int k = n - (j - i + 1);

if (k == m) return 0;

int& ans = cache[i][k];

if (ans != INT_MIN) return ans;

return ans = max(dp(i + 1, j) + nums[i] * multipliers[k],

dp(i, j - 1) + nums[j] * multipliers[k]);

};

return dp(0, n - 1);

}

};

C++/Bottom-UP

// Author: Huahua

class Solution {

public:

int maximumScore(vector<int>& nums, vector<int>& multipliers) {

const int m = multipliers.size();

const int n = nums.size();

// dp[i][j] := max score of using first i elements and last j elements

vector<vector<int>> dp(m + 1, vector<int>(m + 1));

for (int k = 1; k <= m; ++k)

for (int i = 0, j = k - i; i <= k; ++i, --j)

dp[i][j] = max((i ? dp[i - 1][j] + nums[i - 1] * multipliers[k - 1] : INT_MIN),

(j ? dp[i][j - 1] + nums[n - j] * multipliers[k - 1] : INT_MIN));

int ans = INT_MIN;

for (int i = 0; i <= m; ++i)

ans = max(ans, dp[i][m - i]);

return ans;

}

};

花花酱 LeetCode 1769. Minimum Number of Operations to Move All Balls to Each Box

By zxi on February 20, 2021

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the i^th box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the i^th box.

Each answer[i] is calculated considering the initial state of the boxes.

Example 1:

Input: boxes = "110"
Output: [1,1,3]
Explanation: The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

Example 2:

Input: boxes = "001011"
Output: [11,8,5,4,3,4]

Constraints:

n == boxes.length
1 <= n <= 2000
boxes[i] is either '0' or '1'

Solution: Prefix Sum + DP

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> minOperations(string boxes) {

const int n = boxes.size();

vector<int> ans(n);

for (int i = 0, c = 0, s = 0; i < n; ++i) {

ans[i] += c;

c += (s += boxes[i] - '0');

}

for (int i = n - 1, c = 0, s = 0; i >= 0; --i) {

ans[i] += c;

c += (s += boxes[i] - '0');

}

return ans;

}

};

花花酱 LeetCode 1768. Merge Strings Alternately

By zxi on February 20, 2021

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r

Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1:  a   b 
word2:    p   q   r   s
merged: a p b q   r   s

Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1:  a   b   c   d
word2:    p   q 
merged: a p b q c   d

Constraints:

1 <= word1.length, word2.length <= 100
word1 and word2 consist of lowercase English letters.

Solution: Find the shorter one

Time complexity: O(m+n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string mergeAlternately(string word1, string word2) {

const int l1 = word1.size(), l2 = word2.size();

string ans;

for (int i = 0; i < min(l1, l2); ++i) {

ans += word1[i];

ans += word2[i];

}

ans += l1 > l2 ? word1.substr(l2) : word2.substr(l1);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1773. Count Items Matching a Rule

Solution: Brute Force

C++

花花酱 LeetCode 1771. Maximize Palindrome Length From Subsequences

Solution: DP

C++

C++

花花酱 LeetCode 1770. Maximum Score from Performing Multiplication Operations

Solution: DP

C++/Top-Down

C++/Bottom-UP

花花酱 LeetCode 1769. Minimum Number of Operations to Move All Balls to Each Box

Solution: Prefix Sum + DP

C++

花花酱 LeetCode 1768. Merge Strings Alternately

Solution: Find the shorter one

C++